Эта статья находится в разработке!
Рассмотрим автомат, переходы в котором осуществляются по строкам.
| Теорема (О эквивалентности автоматов с переходами по строкам и НКА): |
Автоматы с переходами по строкам эквивалентны недетерминированным автоматам. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим два случая:
- [math]\left | \alpha \right | \ge 1[/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]\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]\varepsilon[/math]-переходов.
- Устранение [math]\varepsilon[/math]-переходов
- Из предыдущего замечания следует, что если теперь устранить [math]\varepsilon[/math]-переходы, то допускаемый язык не изменится. Уберем из [math]A_3[/math] все [math]\varepsilon[/math]-переходы. Получим НКА эквивалентный исходному автомату.
|
| [math]\triangleleft[/math] |
Следствие: множество языков, допускаемых автоматами с [math]\varepsilon[/math]-переходами, совпадает с множеством языков, допускаемых ДКА.
