Имея NFA, есть ли способ определить, принимает ли он все строки, составленные из его алфавита, без необходимости перебирать бесконечное множество возможных строк?
Определение того, принимает ли недетерминированный конечный автомат все возможные строки
Ответы (1)
Конечно! Вот один алгоритм:
- Запустите конструкцию подмножества, чтобы превратить NFA в DFA.
- Минимизируйте DFA, используя алгоритм минимизации DFA.
- Проверьте, состоит ли DFA из одного принимающего состояния. Если это так, исходный NFA принимает все. Если нет, то есть по крайней мере одна строка, которую NFA не принимает.
Может быть более быстрый алгоритм, чем этот (шаг (1) может занять время, экспоненциальное по размеру входного NFA), но это показывает, что действительно существует какой-то алгоритм для решения этой проблемы.
person
templatetypedef
schedule
01.05.2020
