Изменения

==Автомат Автоматы с eps<tex dpi = "155">\varepsilon</tex>-переходами==Рассмотрим Конечный автомат с <tex>\varepsilon</tex>-переходами {{---}} конечный автомат, в котором есть возможность совершать переходы осуществляются по строкам<tex>\varepsilon</tex>. Это переходы вида {{Определение|definition='''<tex>\varepsilon<p,\alpha\beta/tex>\vdash-НКА''' или '''НКА с <q,tex>\beta>varepsilon</tex>, где -переходами''' (англ. ''<tex>\alpha,\betavarepsilon</tex> -moves'') {{--- строки. В случае, когда }} набор <tex>A={\langle\Sigma,Q,s,T,\alpha=delta\varepsilonrangle}</tex>, такой автомат называется '''автоматом с где все компоненты имеют тот же смысл, что и для [[Недетерминированные конечные автоматы|НКА]], за исключением <tex>\delta : Q\times (\Sigma\cup\{\varepsilon\}) \to 2^Q</tex>-переходами.'''}} ==Эквивалентность автоматов с переходами по строкам и НКА. Eps<tex dpi = "155">\varepsilon</tex>-замыкание.==Будем называть два автомата '''эквивалентными''', если они задают один и тот же язык.<br>Рассмотрим автомат, в котором переходы осуществляются по строкам. Это переходы вида <tex>\langle p,\alpha\beta\rangle\vdash\langle q,\beta\rangle</tex>, где <tex>\alpha,\beta</tex> {{---}} строки.{{УтверждениеТеорема

* <tex>\left | \alpha \right | \ge geqslant 1</tex>*:Заменим переходы по таким строкам на последовательности переходов по символам. А именно, пусть <tex>\alpha=a_1a_2...\ldots a_n</tex>, где <tex>a_1,a_2,...\ldots ,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},...\ldots ,{<\langle t_{n-1}, a_n>\beta\rangle\vdash<\langle q, \beta>\rangle}.</tex>

*:Рассматриваем '''автомат <tex>A</tex> с <tex>\varepsilon</tex>-переходами.''' Для доказательства его эквивалентности НКА посторим построим его <tex>\varepsilon</tex>-замыкание.

'''<tex>\varepsilon</tex>-замыкание ''' (англ. ''<tex>\varepsilon</tex>-closure'') {{--- }} построение по автомату с <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,vc)=cw</tex>. Заметим, что если полученный автомат <tex>A_3</tex> допускает <tex>x</tex>, то он допускает <tex>x</tex> , не совершая <tex>\varepsilon</tex>-переходов.

Получили НКА без <tex>\varepsilon</tex>-переходов , эквивалентный исходному автомату.

 ==Совпадение множеств языков, допускаемых eps<tex dpi = "155">\varepsilon</tex>-НКА и ДКА==

|proof=[[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|<tex> \mathcal{L}(</tex>ДКА<tex>) = \mathcal{L}(</tex>НКА<tex>)</tex>]]. По только что доказанной теореме, <tex> \mathcal{L}(</tex>НКА<tex>) = \mathcal{L}(</tex><tex>\varepsilon</tex>-НКА<tex>)</tex>. Значит, <tex> \mathcal{L}(</tex>ДКА<tex>) = \mathcal{L}(</tex><tex>\varepsilon</tex>-НКА<tex>)</tex>.