Изменения
Нет описания правки
{{Определение
|definition =
Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' из <tex>\langle q, \alpha \rangle </tex>, если <tex>\exists nc_1, c_2 \ldots c_n</tex>:* <tex>\langle q, c_1 c_2 c_3 ...\ldots c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...\ldots c_n\beta \rangle \vdash \langle u_2, c_3 ...\ldots c_n\beta \rangle ...\ldots \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>
}}
* <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(\varepsilon) </tex>, будем добавлять <tex> w_1w[1], w_2 w[2] \ldots w_{w[|w|} ] </tex> и находить для каждого <tex> R(w_1w[1]\ldots w_kw[k]) </tex>.
Когда мы получим <tex> R(w) </tex>, проверим, есть ли в нем терминальное состояние.
<tex> R_i = \varnothing </tex>
for <tex> p \in R_{i - 1} </tex> do
<tex> R_i = R_i \cup \delta(p, w_iw[i]) </tex>
accepts = False
for <tex> t \in T </tex> do
