Единственный известный мне способ найти NFA, который принимает дополнение к языку, принятому данным NFA, - это преобразовать NFA в эквивалентный DFA, а затем сделать неконечные состояния конечным состоянием, а конечные состояния - неконечными. Есть ли другой способ добиться того же?
Каковы способы найти недетерминированные конечные автоматы (НКА), которые допускают дополнение языка, принятого данным НКА?
Ответы (2)
В принципе, учитывая NFA A, его можно преобразовать в эквивалентный (в смысле принятия того же языка) DFA B, который, в свою очередь, можно преобразовать в C, сделав каждое конечное состояние нетерминальным, и наоборот, чтобы принять дополнение языка, принятого A.
person
Codor
schedule
28.08.2015
Единственный способ, который я знаю, это ваше решение.
Я чувствую, что должен быть способ доказать, что другого решения не существует. Но я не могу установить доказательство прямо сейчас.
person
abbaasi
schedule
03.09.2015
