въпрос относно автомати

[kliment]

Извинявам се ако въпроса е глупав но търсих навсякъде и не мога да намеря нищо по въпроса как става преминаването от НДА в ДКА.Има ли някакъв алгоритъм, някаква формула относно преходите или просто ако може някой да ми обясни
как стават тези работи:)

[Baronov]

Това, което се сещам сега е да се построи нов автомат в който състоянията са всички подмножество от състояния на стария. Връзка между две подмножества има, ако от съответното множество, което е първото състояние, може да се отиде до някой елемент на второто във недерминирания автомат. Заключителни са тези състояния, чиито множества съдържат заключително състояние. Този автомат очевидно е еквивалентен на НДА и е КДА.

Имаше и някаква процедура, която построяваше минимален КДА еквивалентен на даден, но не си я спомням. Със сигурност я има в книгата на Краси Манев "Дискретна математика"

[ptj]

Извинявам се ако въпроса е глупав но търсих навсякъде и не мога да намеря нищо по въпроса как става преминаването от НДА в ДКА.Има ли някакъв алгоритъм, някаква формула относно преходите или просто ако може някой да ми обясни
как стават тези работи:)

Да, има си такава теорема. "От всеки НДКА може да се получи ДКА". Погледни в сайта на ФМИ-Пловдив дали няма лекции на доц. (или може би професор вече) Степан Костадинов.

След като написах мнението видях, че въпроса е разискван в друг форум и обяснен доста добре.

http://www.math10.com/forumbg/viewtopic.php?t=8746