Мне нужно разработать эффективную процедуру принятия решения, чтобы определить, является ли язык, принятый недетерминированным конечным автоматом, пустым.
Я знаю, что машина не принимает строку, если нет пути от начального состояния к конечному состоянию.
Но я изо всех сил пытаюсь доказать это или разработать процедуру.
Спасибо
Итак, как вы сказали, вы выполняете поиск в глубину или в ширину из начального состояния и печатаете «нет», если вы сталкиваетесь с принимающим состоянием. Если поиск завершается без вывода «нет», выведите «да».
Доказательство того, что это работает, легко, если вы используете DFS в качестве поиска. Затем, выполняя поиск, отслеживайте последовательность символов, которые вы уже встречали на ветке. Если вы дойдете до состояния принятия, строка, которую вы видели, является строкой, принятой DFA; вы можете выплюнуть это как контрпример к пустому языку. Вы не можете получить лучшее доказательство, чем контрпример.
