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

Эта статья находится в разработке!

Рассмотрим автомат, в котором переходы осуществляются по строкам. Это переходы вида [math]\lt p,\alpha\beta\gt \vdash\lt q,\beta\gt [/math], где [math]\alpha,\beta[/math] --- строки.

Теорема (Об эквивалентности автоматов с переходами по строкам и НКА):

Автоматы с переходами по строкам эквивалентны недетерминированным конечным автоматам.

Доказательство:

[math]\triangleright[/math]

Рассмотрим два случая: [math]\left | \alpha \right | \ge 1[/math] Заменим переходы по таким строкам на последовательности переходов по символам. А именно, пусть [math]\alpha=a_1a_2...a_n[/math], где [math]a_1,a_2,...,a_n[/math] --- символы. Заменим переход [math]\lt p,\alpha\beta\gt \vdash\lt q,\beta\gt [/math] на переходы [math]{\lt p,\alpha\beta\gt \vdash\lt t_1, a_1^{-1}\alpha\beta\gt },{\lt t_1,a_1^{-1}\alpha\beta\gt \vdash\lt t_2,(a_1a_2)^{-1}\alpha\beta\gt },...,{\lt t_{n-1}, a_n\gt \vdash\lt q, \beta\gt }.[/math] [math]\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon[/math] Рассматриваем автомат [math]A[/math] с [math]\varepsilon[/math]-переходами. Для доказательства его эквивалентности НКА посторим его [math]\varepsilon[/math]-замыкание. Определение: [math]\varepsilon[/math]-замыкание ([math]\varepsilon[/math]-closure) --- построение по автомату с [math]\varepsilon[/math]-переходами эквивалентного ему автомата без [math]\varepsilon[/math]-переходов. Ход построения [math]\varepsilon[/math]-замыкания: Транзитивное замыкание Пусть [math]B[/math] - подгаф [math]A[/math], в котором есть только [math]\varepsilon[/math]-переходы. Сделаем транзитивное замыкание графа [math]B[/math]. Таким образом, получим из автомата [math]A[/math] новый автомат [math]A_1[/math], который допускает тот же язык. Заметим, что если [math]A_1[/math] допускает слово [math]x[/math], то он допускает [math]x[/math], не совершая двух [math]\varepsilon[/math]-переходов подряд. Добавление допускающих состояний Пусть в [math]A_1[/math] есть [math]\varepsilon[/math]-переход из состояния [math]u[/math] в состояние [math]v[/math], причем [math]v[/math] - допускающее. Тогда, если текущее состояние [math]u[/math] и строка закончилась, то ее можно допустить. Во всех таких случаях сделаем [math]u[/math] допускающим. Получим автомат [math]A_2[/math], обладающий тем же свойством, что и [math]A_1[/math], а также не совершающий [math]\varepsilon[/math]-переходов в качестве последнего перехода. Добавление ребер Во всех случаях, когда [math]{\delta(u,\varepsilon)=v}, {\delta(v,c)=w}[/math] добавим переход [math]\delta(u,v)=c[/math]. Заметим, что если полученный автомат [math]A_3[/math] допускает [math]x[/math], то он допускает [math]x[/math] не совершая [math]\varepsilon[/math]-переходов. Устранение [math]\varepsilon[/math]-переходов Из предыдущего замечания следует, что если теперь устранить [math]\varepsilon[/math]-переходы, то допускаемый язык не изменится. Уберем из [math]A_3[/math] все [math]\varepsilon[/math]-переходы. Получили НКА без [math]\varepsilon[/math]-переходов эквивалентный исходному автомату.

[math]\triangleleft[/math]

Утверждение (Об автоматах с [math]\varepsilon[/math]-переходами и ДКА):

Множество языков, допускаемых автоматами с [math]\varepsilon[/math]-переходами, совпадает с множеством языков, допускаемых детерминированными конечными автоматами.

[math]\triangleright[/math]

L(ДКА) = L(НКА). По только что доказанной теореме, L(НКА) = L([math]\varepsilon[/math]-НКА). Значит, L(ДКА) = L([math]\varepsilon[/math]-НКА).

[math]\triangleleft[/math]