Минимизация конечного автомата

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

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

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

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


computer-science computation-theory turing-machines finite-automata
person user635064    schedule 07.03.2011    source источник
comment
Кажется, это лучше подходит для cstheory.stackexchange.com. Кроме того, вы можете загружать изображения в SO, пожалуйста, не размещайте ссылки на сайты, которые когда-нибудь умрут.   -  person Björn Pollex    schedule 07.03.2011
comment
Этот вопрос кажется не по теме, потому что он касается общей информатики.   -  person Bakuriu    schedule 04.03.2014

Ответы (1)


arrow_upward
0
arrow_downward

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

Глядя на исходный DFA, я не могу придумать никакого решения с менее чем 6 состояниями; но опять же это ничего не значит ;).

person ios k    schedule 04.04.2011