Изменения

'''Недетерминированный конечный автомат''' или НКА (НКАNFA {{---}} Nondeterministic Finite Automaton) {{---}} пятерка пятёрка <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to 2^Q \rangle</tex>, где <tex>\Sigma</tex> {{---}} алфавит, <tex>Q</tex> {{---}} множество состояний автомата, <tex>s</tex> {{---}} начальное состояние автомата, <tex>T</tex> {{---}} множество допускающих состояний автомата, <tex>\delta</tex> {{---}} функция переходов.Таким образом, единственное отличие НКА от [[Детерминированные_конечные_автоматы | ДКА ]] {{---}} существование нескольких переходов по одному символу из одного состояния.

НКА '''допускает''' (accepts) слово <tex>\alpha</tex>, если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.