editor
177
правок
Изменения
м
→Совпадение множеств языков, допускаемых eps-НКА и ДКА
|statement=
Множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых [[Детерминированные_конечные_автоматы|детерминированными конечными автоматами]].
|proof=[[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|<tex> \mathcal{L}(</tex>ДКА<tex>) = \mathcal{L}(</tex>НКА<tex>)</tex>]]. По только что доказанной теореме, L(НКА) = L(<tex>\varepsilon</tex>-НКА). Значит, L(ДКА) = L(<tex>\varepsilon</tex>-НКА).
}}
