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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 4: Строка 4:
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
|about=О эквивалентности автоматов с переходами по строкам и НКА
+
|about=Об эквивалентности автоматов с переходами по строкам и НКА
 
|statement=
 
|statement=
 
Автоматы с переходами по строкам эквивалентны недетерминированным автоматам.
 
Автоматы с переходами по строкам эквивалентны недетерминированным автоматам.
Строка 24: Строка 24:
 
#:Во всех случаях, когда <tex>\delta(u,\varepsilon)=v,\delta(v,c)=w</tex> добавим переход <tex>\delta(u,v)=c</tex>. Заметим, что если полученный автомат <tex>A_3</tex> допускает <tex>x</tex>, то он допускает его не совершая <tex>\varepsilon</tex>-переходов.
 
#:Во всех случаях, когда <tex>\delta(u,\varepsilon)=v,\delta(v,c)=w</tex> добавим переход <tex>\delta(u,v)=c</tex>. Заметим, что если полученный автомат <tex>A_3</tex> допускает <tex>x</tex>, то он допускает его не совершая <tex>\varepsilon</tex>-переходов.
 
#Устранение <tex>\varepsilon</tex>-переходов
 
#Устранение <tex>\varepsilon</tex>-переходов
#:Из предыдущего замечания следует, что если теперь устранить <tex>\varepsilon</tex>-переходы, то допускаемый язык не изменится. Уберем из <tex>A_3</tex> все <tex>\varepsilon</tex>-переходы. Получим НКА эквивалентный исходному автомату.
+
#:Из предыдущего замечания следует, что если теперь устранить <tex>\varepsilon</tex>-переходы, то допускаемый язык не изменится. Уберем из <tex>A_3</tex> все <tex>\varepsilon</tex>-переходы.
 +
Получили НКА без <tex>\varepsilon</tex>-переходов эквивалентный исходному автомату.
 +
}}
 +
{{Утверждение
 +
|id=th1
 +
|about=Об автоматах с <tex>\varepsilon</tex>-переходами и ДКА
 +
|statement=
 +
Множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых ДКА.
 +
|proof=
 
}}
 
}}
'''Следствие:''' множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых ДКА.
 

Версия 05:43, 5 октября 2010

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

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

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

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