333
правки
Изменения
Нет описания правки
</tex>
В силу конечности множеств состояний автомата (<tex> Q </tex>) и алфавита (<tex> T </tex>) добавим все подобные правила (представленные выше) в нашу полусистему. Заметим, что в МТ лента у нас бесконечна. Поэтому добавим в нашу систему следующие правила, которые будут эмулировать расширение слова на ленте за счет сдвига маркера <tex> | </tex>(прим. B {{---}} пустой символ ленты) :
<tex>q| \rightarrow q0qB| </tex> и <tex>|q \rightarrow |0q Bq </tex> для <tex> \forall q \in Q \setminus \{q_n\}</tex>
И наконец добавим в наш набор те правила, которые позволят нам из конфигурации, в которой присутствует допускающее состояние <tex> q_n </tex>, получить уникальное слово. Это необходимо, чтобы мы смогли построить критерий в терминах полуситсемы Туэ того, что из стартовой конфигураций наша программа корректно завершается. Имеем следующие правила:
