Алгоритм, который проверяет, генерирует ли контекстно-свободная грамматика бесконечный язык, который отклоняет DFA

Question

У меня есть DFA A и CFG G, тогда я должен проверить, генерирует ли G бесконечные слова, которые A не принимает (отклоненные A), и хорошее время сложности.

Я думал построить граф с CFG, и если он содержит направленный цикл, то производит бесконечный язык. Вершины - это переменные, и для каждого производства я рисую некоторые ребра. Входные данные - это все слова, отклоненные DFA, и когда я нашел цикл, я могу сказать, что CFG генерирует бесконечный язык, отклоненный DFA A.

Я не знаю, как преобразовать его в алгоритм или если мое предложение неверно, и мне нужно создать новое.

Редактировать: Могу ли я преобразовать свой CFG в CNF, а затем в DFA (с chomsky). После этого я пытаюсь найти цикл. Но у моего преобразованного dfa может быть меньше состояний, чем у моего dfa a... Мне нужно, как получить слова, отклоненные DFA A в моем cfg, я думаю.

Answer 1

Учитывая CFG G, построить PDA B. Учитывая DFA A и PDA B, построить PDA C таким образом, что C принимает L(C) = L(B) \ L(A), где \ - заданная разница. Теперь L (C) - это в точности язык слов, принятый КПК B (следовательно, сгенерированный CFG G), но не принятый, то есть отклоненный DFA A.

Теперь вопрос в том, является ли язык B бесконечным. Мы можем это сделать. Один из способов - преобразовать КПК обратно в CFG, а затем поместить CFG в CNF, удалив ненужные и непродуктивные символы. Затем создайте дерево зависимостей среди нетерминальных символов. Если какой-либо оставшийся (производительный) нетерминальный символ зависит от самого себя, т. Е. Существует петля, то язык бесконечен. В противном случае язык является конечным (пустым, если не осталось продуктивных символов).