editor
177
правок
Изменения
м
Нет описания правки
== Алгоритм, определяющий допустимость автоматом слова ==
Этот алгоритм решает такую следующую задачу: заданы НКА и слово, нужно определить допускает ли НКА данное слово. По сравнению с ДКА, определять определить, допускает ли НКА слово , сложнее, так как из состояния теперь есть несколько переходов по букве и выбрать случайный переход нельзя. Поступим по-другому, : определим множество всех достижимых состояний из стартового по слову <tex> \alpha </tex>.
* <tex> R(\alpha) = \lbrace p | \langle s, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle \rbrace </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>, проверим что , есть ли в нем есть терминальное состояние.
Псевдокод:
</font>
Время работы этого алгоритма будет : <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>.
== См. также ==
