Автоматы с 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]-замыкания:

  1. Транзитивное замыкание
  2. Допускающие состояния
  3. Добавление ребер
  4. Устранение [math]\varepsilon[/math]-переходов
Получили НКА эквивалентный исходному автомату.
[math]\triangleleft[/math]

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