Минимизирующий конечный государственный автомат - PullRequest
1 голос
/ 07 марта 2011

Я пытаюсь минимизировать этот DFA: http://img145.imageshack.us/img145/3006/dfac.png

Вот мой свернутый DFA: http://img195.imageshack.us/img195/4131/mdfa.png

Я прав?Спасибо

PS - это домашнее задание.Нам разрешено обсуждать домашнее задание.Я не спрашиваю ответа, я просто хочу знать, нахожусь ли я на правильном пути или нет, поскольку я впервые имею дело с конечными автоматами.

1 Ответ

0 голосов
/ 04 апреля 2011

Нет, предложенное вами решение неверно;вы видите, что построенная вами dfa может принять (иначе неприемлемую) строку «aac», что означает, что вы не можете объединять состояния (11,15,17) и (15,17).

Lookingв исходном DFA я не могу придумать никакого решения с менее чем 6 состояниями;но опять же это ничего не значит;).

...