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