211
правок
Изменения
м
Нет описания правки
|definition=
'''Недетерминированный конечный автомат''' (НКА) {{---}} пятерка <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> {{---}} функция переходов.
Таким образом , единственное отличие НКА от ДКА {{---}} существование нескольких переходов по одному символу из одного состояния.
}}
{{Определение
|definition =
'''Мгновенная кофигурация''' {{---}} пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>.}}
Определим некоторые операции для мгновенных конфигураций.
|definition =
Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за один шаг''' из <tex>\langle q, \alpha \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> \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>.
}}
|definition =
Множество слов, допускаемых автоматом <tex> \mathcal{A} </tex>, называется '''языком НКА''' <tex> \mathcal{A} </tex>.
* <tex> \mathcal{L}(\mathcal{A}) = \lbrace w | \exists t \in T : \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle \rbrace </tex>.
}}
== Алгоритм, определяющий допустимость автоматом слова ==
Этот алгоритм решает следующую задачу: заданы НКА и слово, нужно определить , допускает ли НКА данное слово.
По сравнению с ДКА, определить, допускает ли НКА слово, сложнее, так как из состояния теперь есть несколько переходов по букве и выбрать случайный переход нельзя.
