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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} Рассмотрим автомат, переходы в котором осуществляются по строкам. {{Теорем…»)
 
Строка 13: Строка 13:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
<tex>\varepsilon</tex>-замыкание (eps-closure) --- построение по автомату с <tex>\varepsilon</tex>-переходами эквивалентного ему автомата без <tex>\varepsilon</tex>-переходов.
+
<tex>\varepsilon</tex>-замыкание (<tex>\varepsilon</tex>-closure) --- построение по автомату с <tex>\varepsilon</tex>-переходами эквивалентного ему автомата без <tex>\varepsilon</tex>-переходов.
 
}}
 
}}
 
Ход построения <tex>\varepsilon</tex>-замыкания:
 
Ход построения <tex>\varepsilon</tex>-замыкания:

Версия 21:49, 25 сентября 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]-переходами, совпадает с множеством языков, допускаемых ДКА.