Изменения

Этот алгоритм решает следующую задачу: ===Постановка задачи===Пусть заданы НКА и слово<tex>w</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> \forall q \in \delta(p, c) </tex>