57
правок
Изменения
Нет описания правки
* <tex>\left | \alpha \right | \ge 1</tex>
* <tex>\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon</tex>
*:Рассматриваем '''автомат А <tex>A</tex> с <tex>\varepsilon</tex>-переходами.''' Для доказательства его эквивалентности НКА посторим его <tex>\varepsilon</tex>-замыкание.*:{{Определение
|definition=
<tex>\varepsilon</tex>-замыкание (<tex>\varepsilon</tex>-closure) --- построение по автомату с <tex>\varepsilon</tex>-переходами эквивалентного ему автомата без <tex>\varepsilon</tex>-переходов.
Ход построения <tex>\varepsilon</tex>-замыкания:
#Транзитивное замыкание
#Допускающие :Пусть <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>\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,v)=c</tex>. Заметим, что если полученный автомат <tex>A_3</tex> допускает <tex>x</tex>, то он допускает его не совершая <tex>\varepsilon</tex>-переходов.
#Устранение <tex>\varepsilon</tex>-переходов
}}
'''Следствие:''' множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых ДКА.
