333
правки
Изменения
Нет описания правки
<tex>q \rangle \rightarrow qB \rangle </tex> и <tex>\langle q \rightarrow \langle Bq </tex> для <tex> \forall q \in Q \setminus \{q_n\}</tex>
И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. Имеем При этом пусть это уникальное слово имеет вид <tex> \langle w \rangle </tex>, где <tex> w \notin T </tex>. Таким образом, имеем следующие правила:
<tex>q_n c \rightarrow q_n </tex> для <tex> \forall c \in T</tex>
<tex>q_n \rangle \rightarrow w \rangle </tex> для некоторого фиксированного для всех таких правил символа <tex> w \notin T </tex>
<tex> c w \rightarrow w </tex> для <tex> \forall c \in T</tex>.
