57
правок
Изменения
м
|about=Об эквивалентности автоматов с переходами по строкам и НКА
Нет описания правки
{{В разработке}}
[[Категория: Теория формальных языков]]
==Автомат с eps-переходами==Рассмотрим автомат, в котором переходы осуществляются по строкам. Это переходы вида <tex><p,\alpha\beta>\vdash<q,\beta></tex>, где <tex>\alpha,\beta</tex> --- строки.В случае, когда <tex>\alpha=\varepsilon</tex>, такой автомат называется '''автоматом с <tex>\varepsilon</tex>-переходами.'''==Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание.=={{ТеоремаУтверждение
|id=th1
|statement=
Автоматы с переходами по строкам эквивалентны [[Недетерминированные_конечные_автоматы|недетерминированным конечным автоматам]].
Получили НКА без <tex>\varepsilon</tex>-переходов эквивалентный исходному автомату.
}}
==Совпадение множеств языков, допускаемых eps-НКА и ДКА==
{{Утверждение
|id=th1|about=Об автоматах с <tex>\varepsilon</tex>-переходами и ДКАth2
|statement=
Множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых [[Детерминированные_конечные_автоматы|детерминированными конечными автоматами]].
|proof=[[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|L(ДКА) = L(НКА)]]. По только что доказанной теореме, L(НКА) = L(<tex>\varepsilon</tex>-НКА). Значит, L(ДКА) = L(<tex>\varepsilon</tex>-НКА).
}}
