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