57
правок
Изменения
Новая страница: «{{В разработке}} Рассмотрим автомат, переходы в котором осуществляются по строкам. {{Теорем…»
{{В разработке}}
Рассмотрим автомат, переходы в котором осуществляются по строкам.
{{Теорема
|id=th1
|about=О эквивалентности автоматов с переходами по строкам и НКА
|statement=
Автоматы с переходами по строкам эквивалентны недетерминированным автоматам.
|proof=
Рассмотрим два случая:
* <tex>\left | \alpha \right | \ge 1</tex>
* <tex>\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon</tex>
Рассматриваем '''автомат А с <tex>\varepsilon</tex>-переходами.''' Для доказательства его эквивалентности НКА посторим его <tex>\varepsilon</tex>-замыкание.
{{Определение
|definition=
<tex>\varepsilon</tex>-замыкание (eps-closure) --- построение по автомату с <tex>\varepsilon</tex>-переходами эквивалентного ему автомата без <tex>\varepsilon</tex>-переходов.
}}
Ход построения <tex>\varepsilon</tex>-замыкания:
#Транзитивное замыкание
#Допускающие состояния
#Добавление ребер
#Устранение <tex>\varepsilon</tex>-переходов
Получили НКА эквивалентный исходному автомату.
}}
'''Следствие:''' множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых ДКА.
Рассмотрим автомат, переходы в котором осуществляются по строкам.
{{Теорема
|id=th1
|about=О эквивалентности автоматов с переходами по строкам и НКА
|statement=
Автоматы с переходами по строкам эквивалентны недетерминированным автоматам.
|proof=
Рассмотрим два случая:
* <tex>\left | \alpha \right | \ge 1</tex>
* <tex>\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon</tex>
Рассматриваем '''автомат А с <tex>\varepsilon</tex>-переходами.''' Для доказательства его эквивалентности НКА посторим его <tex>\varepsilon</tex>-замыкание.
{{Определение
|definition=
<tex>\varepsilon</tex>-замыкание (eps-closure) --- построение по автомату с <tex>\varepsilon</tex>-переходами эквивалентного ему автомата без <tex>\varepsilon</tex>-переходов.
}}
Ход построения <tex>\varepsilon</tex>-замыкания:
#Транзитивное замыкание
#Допускающие состояния
#Добавление ребер
#Устранение <tex>\varepsilon</tex>-переходов
Получили НКА эквивалентный исходному автомату.
}}
'''Следствие:''' множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых ДКА.
