Изменения
→Процесс допуска
|definition =
Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' из <tex>\langle q, \alpha \rangle </tex>, если <tex>\exists c_1, c_2 \ldots c_n</tex>:
* <tex>\langle q, c_1 c_2 \ldots c_n \beta\rangle \vdash \langle u_1, c_2 c_3 \ldots c_n \beta\rangle \vdash \langle u_2, c_3 \ldots c_n \beta\rangle \ldots \vdash \langle u_{n-1}, c_n \beta\rangle \vdash \langle p, \beta \rangle</tex>.
Это также записывают так: <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>.
}}
Менее формально это можно описать так: НКА допускает слово <tex> \alpha </tex>, если существует путь из начального состояния в какое-то терминальное, такое что буквы, выписанные с переходов на этом пути по порядку, образуют слово <tex> \alpha </tex>.
== Язык автомата ==
