308
правок
Изменения
м
Нет описания правки
{{Определение
|definition =
[[Транзитивное замыкание#Рефлексивно-транзитивное замыкание | Рефлексивно-транзитивное замыкание ]] отношения <tex> \vdash </tex> обозначается как <tex> \vdash^*</tex>. <br>
И говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' (англ. ''yields'') из <tex>\langle q, \alpha \rangle </tex>, если <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>.
<!--Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' (англ. ''yields'') из <tex>\langle q, \alpha \rangle </tex>, если <tex>\exists c_1, c_2 \ldots c_n</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(\alpha) </tex> строить <tex> R(\alpha c)</tex>, возьмем <tex> R(\varepsilon) </tex> и будем последовательно вычислять <tex>R(w[1]\ldots w[k])</tex> для <tex>k=1..\ldots |w|</tex>.
Таким образом, мы получим <tex>R(w)</tex>, и всё, что осталось — проверить, есть ли в нём терминальное состояние.
