Определение того, принимает ли недетерминированный конечный автомат c каждую возможную строку

Question

Учитывая NFA, есть ли способ определить, принимает ли он все строки, построенные из его алфавита, без необходимости перебирать бесконечный набор возможных строк?

Answer 1

Конечно! Вот один алгоритм:

1. Запустите конструкцию подмножества, чтобы превратить NFA в DFA.
2. Минимизировать DFA, используя алгоритм минимизации DFA.
3. Проверьте, включен ли DFA состоит из единственного государства, которое принимает. Если это так, оригинальный NFA принимает все. Если нет, то есть хотя бы одна строка, которую NFA не принимает.

Возможно, алгоритм быстрее, чем этот (шаг (1) может занять экспоненциальное по времени значение размера входного NFA), но это показывает, что действительно существует некоторый алгоритм для решения этой проблемы.