Изменения

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

== Способ хранения Алгоритм определяющий допустимость автоматом слова == По сравнению с ДКА, определять допускает ли НКА слово сложнее, так как из состояния теперь есть несколько переходов по букве и выбрать случайный переход нельзя. Поступим по-другому, определим множество всех достижимых состояний из стартового по слову <tex> \alpha </tex>. * <tex> R(\alpha) = \lbrace p | \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace </tex>

== Пусть нам нужно определить допускает ли НКА слово <tex> w </tex>. Заметим, что если <tex> \exists t \in T : t \in R(w) </tex>, то слово допускается, так как <tex> \langle s, w \rangle \vdash^* \langle t, \varepsilon \rangle </tex> по определению <tex> R(w) </tex>. Алгоритм определяющий допустимость автоматом слова состоит в том, чтобы построить <tex> R(w) </tex>. Очевидно, что <tex> R(\varepsilon) =\lbrace s \rbrace </tex>. Пусть мы построили <tex> R(\alpha) </tex>, как же получить <tex> R(\alpha c)</tex>, где <tex> c \in \Sigma </tex>. Заметим, что * <tex> R(\alpha c) =\lbrace q | q \in \delta(p, c), p \in R(\alpha) \rbrace </tex>, так как * <tex> \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle p, c \rangle \vdash \langle q, \varepsilon \rangle \Rightarrow \langle s, \alpha c \rangle \vdash^* \langle q, \varepsilon \rangle </tex>, где <tex> q \in \delta(p, c) </tex> Теперь, когда мы научились добавлять символ к строке, возьмем <tex> R(\varepsilon) </tex>, будем добавлять <tex> w_1, w_2 \ldots w_{|w|} </tex> и находить для каждого <tex> R(w_1\ldots w_k) </tex>. Когда мы получим <tex> R(w) </tex>, проверим что в нем есть терминальное состояние.