Автоматы с eps-переходами. Eps-замыкание — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 +
[[Категория: Теория формальных языков]]
 
Рассмотрим автомат, переходы в котором осуществляются по строкам.
 
Рассмотрим автомат, переходы в котором осуществляются по строкам.
 
{{Теорема
 
{{Теорема

Версия 23:06, 30 сентября 2010

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

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

Теорема (О эквивалентности автоматов с переходами по строкам и НКА):
Автоматы с переходами по строкам эквивалентны недетерминированным автоматам.
Доказательство:
[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]-переходами, совпадает с множеством языков, допускаемых ДКА.