57
правок
Изменения
м
'''Следствие:''' множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых ДКА.
Нет описания правки
{{Теорема
|id=th1
|about=О Об эквивалентности автоматов с переходами по строкам и НКА
|statement=
Автоматы с переходами по строкам эквивалентны недетерминированным автоматам.
#:Во всех случаях, когда <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>A_3</tex> все <tex>\varepsilon</tex>-переходы. Получим Получили НКА без <tex>\varepsilon</tex>-переходов эквивалентный исходному автомату.}}{{Утверждение|id=th1|about=Об автоматах с <tex>\varepsilon</tex>-переходами и ДКА|statement=Множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых ДКА.|proof=
}}
