Недетерминированный Xor автомат (NXA) является синтаксически NFA, но говорят, что NXA принимает слово, если оно имеет нечетное число принимающих путей (вместо хотя бы одного принимающего пути в случае NFA). Легко видеть, что для конечного регулярного языка LLL существует минимальный NFA, который не...
Остаточные автоматы в конечном состоянии (RFSA, определенные в [DLT02]) - это NFA, которые имеют некоторые общие черты с DFA. В частности, для каждого обычного языка всегда существует канонический RFSA минимального размера, а язык, распознаваемый каждым государством в RFSA, является остаточным, как...
Алгоритм Бжозовского для преобразования DFA в эквивалентный DFA с минимальным состоянием удивительно прост: если R(D)R(D)R(D) обозначает NFA, образованный путем обращения всех ребер в DFA DDDпревращение старого начального состояния в принимающее состояние и превращение старого принимающего...