Изменения

<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>.

Теперь, когда мы научились добавлять символ к строкепо <tex> R(\alpha) </tex> строить <tex> R(\alpha c)</tex>, возьмем <tex> R(\varepsilon) </tex>, и будем добавлять последовательно вычислять <tex> R(w[1], w[2] \ldots w[|w|k] )</tex> и находить для каждого <tex> R(w[k=1]\ldots ..|w[k]) |</tex>.

Когда Таким образом, мы получим <tex> R(w) </tex>, проверими всё что осталось — проверить, есть ли в нем нём терминальное состояние.