Просмотр исходного текста страницы Автоматы с eps-переходами. Eps-замыкание

[[Категория: Теория формальных языков]]
==Автоматы с eps-переходами==
Конечный автомат с <tex>\varepsilon</tex>-переходами --- конечный автомат, в котором есть возможность совершать переходы по <tex>\varepsilon</tex>. 
{{Определение
|definition=<tex>\varepsilon</tex>-НКА <tex>A</tex> --- это набор <tex>A={\langle\Sigma,Q,s,T,\delta\rangle}</tex>, где все компоненты имеют тот же смысл, что и для [[Недетерминированные конечные автоматы|НКА]], за исключением <tex>\delta : Q\times \Sigma\bigcup\{\varepsilon\} \to \cal P</tex><tex>(Q)</tex>.
}}
==Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание==
Рассмотрим автомат, в котором переходы  осуществляются по строкам. Это переходы вида <tex>\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle</tex>, где <tex>\alpha,\beta</tex> --- строки.
{{Теорема
|id=th1
|statement=
Автоматы с переходами по строкам эквивалентны [[Недетерминированные_конечные_автоматы|недетерминированным конечным автоматам]].
|proof=
Рассмотрим два случая:
* <tex>\left | \alpha \right | \ge 1</tex>
*:Заменим переходы по таким строкам на последовательности переходов по символам. А именно, пусть <tex>\alpha=a_1a_2...a_n</tex>, где <tex>a_1,a_2,...,a_n</tex> --- символы. Заменим переход <tex>\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle</tex> на переходы <tex>{\langle p,\alpha\beta\rangle\vdash\langle t_1, a_1^{-1}\alpha\beta\rangle},{\langle t_1,a_1^{-1}\alpha\beta\rangle\vdash\langle t_2,(a_1a_2)^{-1}\alpha\beta\rangle},...,{\langle t_{n-1}, a_n\rangle\vdash\langle q, \beta\rangle}.</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>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>-переходов
#:Из предыдущего замечания следует, что если теперь устранить <tex>\varepsilon</tex>-переходы, то допускаемый язык не изменится. Уберем из <tex>A_3</tex> все <tex>\varepsilon</tex>-переходы.
Получили НКА без <tex>\varepsilon</tex>-переходов эквивалентный исходному автомату.
}}

==Совпадение множеств языков, допускаемых eps-НКА и ДКА==
{{Утверждение
|id=th2
|statement=
Множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых [[Детерминированные_конечные_автоматы|детерминированными конечными автоматами]].
|proof=[[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|L(ДКА) = L(НКА)]]. По только что доказанной теореме, L(НКА) = L(<tex>\varepsilon</tex>-НКА). Значит, L(ДКА) = L(<tex>\varepsilon</tex>-НКА).
}}