Изменения

|definition='''<tex>\varepsilon</tex>-НКА''' или '''НКА с <tex>\varepsilon</tex>-переходами'''(англ. ''<tex>\varepsilon</tex>-moves'') {{---}} набор <tex>A={\langle\Sigma,Q,s,T,\delta\rangle}</tex>, где все компоненты имеют тот же смысл, что и для [[Недетерминированные конечные автоматы|НКА]], за исключением <tex>\delta : Q\times (\Sigma\cup\{\varepsilon\}) \to 2^Q</tex>.

#:Пусть в <tex>A_1</tex> есть <tex>\varepsilon</tex>-переход из состояния <tex>u</tex> в состояние <tex>v</tex>, причем <tex>v</tex> {{---}} допускающее. Тогда, если текущее состояние <tex>u</tex> и строка закончилась, то ее её можно допустить. Во всех таких случаях сделаем <tex>u</tex> допускающим. Получим автомат <tex>A_2</tex>, обладающий тем же свойством, что и <tex>A_1</tex>, а также не совершающий <tex>\varepsilon</tex>-переходов в качестве последнего перехода.#Добавление реберрёбер

Эпсилон-замыкание и эквивалентность множества языков, допускаемых ДКА, НКА и <tex>\varepsilon</tex>-НКА, доказанная через него выше, открывают нам новые возможности. В некоторых случаях НКА с <tex>\varepsilon</tex>-переходами в некоторых случаях строятся проще, чем просто НКА и тем более ДКА для тех же языков. При Доказанная выше эквивалентность <tex> \mathcal{L}(</tex>ДКА<tex>)</tex>,<tex>\mathcal{L}(</tex>НКА<tex>)</tex> и <tex>\mathcal{L}(</tex><tex>\varepsilon</tex>-НКА<tex>)</tex> позволяет нам при помощи алгоритма <tex>\varepsilon</tex>-замыкания мы умеем легко приводить одно к другому и далее к третьему. Также свойства, доказанные выше, являются важной составляющей доказательства [[Теорема Клини (совпадение классов автоматных и регулярных языков)| теоремы Клини]].

==Источникиинформации==*[http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton Wikipedia — Nondeterministic finite automaton]*[http://en.wikipedia.org/wiki/Nondeterministic_finite_automaton_with_%CE%B5-moves| Wikipedia — Nondeterministic finite automaton with epsilon-moves]