105
правок
Изменения
м
*[http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton Wikipedia — Nondeterministic finite automaton]
ё
#:Пусть <tex>B</tex> {{---}} подграф <tex>A</tex>, в котором есть только <tex>\varepsilon</tex>-переходы. Сделаем транзитивное замыкание графа <tex>B</tex>. Таким образом, получим из автомата <tex>A</tex> новый автомат <tex>A_1</tex>, который допускает тот же язык. Заметим, что если <tex>A_1</tex> допускает слово <tex>x</tex>, то он допускает <tex>x</tex>, не совершая двух <tex>\varepsilon</tex>-переходов подряд.
#Добавление допускающих состояний
#:Пусть в <tex>A_1</tex> есть <tex>\varepsilon</tex>-переход из состояния <tex>u</tex> в состояние <tex>v</tex>, причем <tex>v</tex> {{---}} допускающее. Тогда, если текущее состояние <tex>u</tex> и строка закончилась, то ее её можно допустить. Во всех таких случаях сделаем <tex>u</tex> допускающим. Получим автомат <tex>A_2</tex>, обладающий тем же свойством, что и <tex>A_1</tex>, а также не совершающий <tex>\varepsilon</tex>-переходов в качестве последнего перехода.#Добавление реберрёбер
#:Во всех случаях, когда <tex>{\delta(u,\varepsilon)=v}, {\delta(v,c)=w}</tex>, добавим переход <tex>\delta(u,c)=w</tex>. Заметим, что если полученный автомат <tex>A_3</tex> допускает <tex>x</tex>, то он допускает <tex>x</tex>, не совершая <tex>\varepsilon</tex>-переходов.
#Устранение <tex>\varepsilon</tex>-переходов
==См. также==
*[[Недетерминированные конечные автоматы]]
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
==Источники информации==
*[http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton Wikipedia — Nondeterministic finite automaton]
*[http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton_with_%CE%B5-moves Wikipedia — Nondeterministic finite automaton with epsilon-moves]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
