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

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

Рассмотрим автомат, переходы в котором осуществляются по строкам.

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

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

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

[math]\triangleright[/math]

Рассмотрим два случая: [math]\left | \alpha \right | \ge 1[/math] [math]\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon[/math] Рассматриваем автомат А с [math]\varepsilon[/math]-переходами. Для доказательства его эквивалентности НКА посторим его [math]\varepsilon[/math]-замыкание. Определение: [math]\varepsilon[/math]-замыкание ([math]\varepsilon[/math]-closure) --- построение по автомату с [math]\varepsilon[/math]-переходами эквивалентного ему автомата без [math]\varepsilon[/math]-переходов. Ход построения [math]\varepsilon[/math]-замыкания: Транзитивное замыкание Допускающие состояния Добавление ребер Устранение [math]\varepsilon[/math]-переходов Получили НКА эквивалентный исходному автомату.

[math]\triangleleft[/math]

Следствие: множество языков, допускаемых автоматами с [math]\varepsilon[/math]-переходами, совпадает с множеством языков, допускаемых ДКА.