18
правок
Изменения
→Недетерминированный конечный автомат
Таким образом НКА - это автомат с возможностью нескольких переходов по одному символу из одного состояния.
}}
Определим некоторые обозначенияя для НКА:
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если:
** <tex>\alpha = c\beta</tex>
** <tex>p \in \delta (q, c)</tex>
* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если <tex>\exists n</tex>:
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>
=== Процесс допуска ===
Автомат допускает слово <tex>\alpha</tex> если <tex>\exists t \in T: \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle</tex>.
Процесс допуска происходит так же, как в ДКА в котором Мерлин помогает выбрать правильный переход.
=== Язык автомата ===
