Вычислительный автомат для $ l (A) / L (B) $ дает за $ a, b $

Question

Я пытаюсь выяснить, изменяет ли бесконечный язык ответа.

Показать, что следующий язык является разрешенным: $$ l={\ langle a, b \ \ \ \ langle a, b \ rangle: \ text {$ a, b $ - dfas, $ l (b) $ конечно, а $ l (a) / L (b)= l (0 ^ * 1 ^ *) $} \}. $$

(я говорю о правильном разделе.)

Мы знаем, как проверить, является ли язык DFA конечным, и данные два DFAS, мы знаем, как проверить, равны ли их языки. Алгоритмы, которые я знаю к вышеуказанным проблемам, использует DFA, поэтому надо иметь DFA, чтобы решить эти проблемы.

Я пытаюсь выяснить, стоит ли $ | l (b) |=infty $ Отменяет ответ. В лучшее из моего понимания, потому что $ | l (b) | <\ infty $ , мы можем явно построить DFA, который принимает $ L (a) / l (b) $ , тогда как если $ l (b)=infty $ Все, что мы знаем, о существовании $ DFA $ , который принимает $ l (a) / l (b) $ .

Однако, даже если $ l (b) $ - это бесконечный язык, поскольку есть конечное число DFA, один из которых принимает $ l (a) / l (b) $ , я могу, безусловно, знал, что есть Turging Machine, которая решает язык $ l $ . Верно?

Answer 1

Что вы действительно спрашиваете, - это ли данные автоматы $ a, b $ , мы можем построить автомат, язык которого является левым лицом $$ L (a) \ backslash l (b)={w: \ существует x \ in \ sigma ^ * \ text {s.t. } x \ in l (a) \ text {и} xw \ in l (b) \}. $$ (Тем временем вопрос изменился для обозначения правильного частного лица, который может быть обработан аналогичным образом.)

Вот такая конструкция. Предположим, что $ a, b $ - это DFAS с состояниями $ q_a, q_b $ , начальные состояния $ q_ {0a}, q_ {0b} $ , переходные функции $ \ delta_a, \ delta_b $ и конечные состояния $ f_a, f_b $ . Мы строим NFA с состояниями $ q= (\ {0 \} \ times q_a \ times q_b) \ cup (\ {1 \} \ times q_b) $ , Начальное состояние $ \ lange 0, q_ {0a}, q_ {0b} \ pangle $ , конечные состояния $ \ {1 \} \ times f_b $ и следующая функция перехода $ \ delta $ :

.
• $ \ delta (\ langle 0, \ langle 0, q_a, \ \ \ langle 0, \ delta_a (\ lange 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ sigma) \ rungle: \ sigma \ in \ sigma \} $ Для всех $ q_a \ in q_a \ setminus f_a $ и $ q_b \ in q_b $ .
• $ \ delta (\ langle 0, \ langle 0, q_a, \ \ \ langle 0, \ delta_a (\ lange 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ sigma) \ range: \ sigma \ in \ sigma \} \ cub \ {\ lange 1, q_b \ pangle \} $ для всех $ q_a \ in f_a $ и $ q_b \ in q_b $ .
• $ \ delta (\ lange 1, \ \ rangle, \ sigma)={\ langle 1, \ delta_b (\ \ lange 1, \ delta_b (q_b, \ sigma) \ rungle \} $ Для всех $ \ sigma \ in \ sigma $ и $ q_b \ in q_b $ .

Answer 2

Это отвечает на другую версию вопроса, в котором рассматриваемый язык - $ l (a) \ setminus l (b) $ .

Вот алгоритм для решения $ l $ :

.
• Используйте конструкцию продукта, чтобы построить DFA $ C $ , язык которого $ l (a) \ setminus l ( Б) $ .
• Пусть $ d $ - это DFA, язык которого является $ 0 ^ * 1 ^ * $ . < / li>
• Используйте конструкцию продукта снова, чтобы построить DFA $ E $ , чей язык - $ l (C) \ delta l (D) $ .
• Проверьте (используя BFS / DFS), будь то конечное состояние $ e $ достижимо от его начального состояния.
• Выход "Да", если от первоначального состояния нет окончательного состояния. В противном случае вывод "нет".

Как вы можете видеть, столкнулись ли языки по пути, конечно или бесконечно, делает абсолютно никакой разницы для этого алгоритма.