Изменения

Перейти к: навигация, поиск

Автоматы с eps-переходами. Eps-замыкание

54 байта добавлено, 09:06, 17 января 2012
м
Совпадение множеств языков, допускаемых 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>-НКА).
}}
editor
177
правок

Навигация