211
правок
Изменения
м
→Алгоритм, определяющий допустимость автоматом слова
== Алгоритм, определяющий допустимость автоматом слова ==
Этот алгоритм решает следующую задачу: заданы НКА и слово, нужно . Требуется определить, допускает ли НКА данное слово.
По сравнению с ДКА, определить, допускает ли НКА слово, сложнее, так как из состояния теперь есть несколько переходов по букве и выбрать случайный переход нельзя.
Когда мы получим <tex> R(w) </tex>, проверим, есть ли в нем терминальное состояние.
===Псевдокод:<font size = 3>== <tex> R_0 = \lbrace s \rbrace </tex> for i = 1 to length(w) do <tex> R_i = \varnothing </tex> for <tex> p \in R_{i - 1} </tex> do <tex> R_i = R_i \cup \delta(p, w[i]) </tex> accepts = False for <tex> t \in T </tex> do if <tex> t \in R_{|w|} </tex> then accepts = True</font>
Время работы алгоритма: <tex> \mathop O(|w|\sum\limits_{t \in Q} \sum\limits_{c \in \Sigma} |\delta(t, c)|) </tex>.
== См. также ==
