171
правка
Изменения
Нет описания правки
<tex>a_i = \$</tex>, <tex>b_i = \$</tex>;
для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \leftarrow \rangle</tex> и для всех символов алфавита <tex>e</tex>:
<tex>a_i = \#_q e d</tex>, <tex>b_i = c e \#_pc</tex>;
для всех правил <tex>M</tex> вида <tex>\delta (p, c) = \langle q, d, \rightarrow \rangle</tex>:
}}
=== Пример ===
Пусть автомат МТ состоит из двух состояний <tex>start</tex> и <tex>yes</tex>, алфавит ленты содержит символы <tex>a</tex> и <tex>b</tex>. Переходы автомата устроены следующим образом:
<tex>\delta (start, a) = \langle start, b, \rightarrow \rangle</tex>;
<tex>\delta (start, b) = \langle yes, b, \downarrow \rangle</tex>;
из <tex>yes</tex> переходов нет.
Последовательности при строке <tex>ab</tex> будут сформированы следующим образом:
{| border="1"
|Номер элемента
|width="45"|1
|width="45"|2
|width="45"|3
|width="45"|4
|width="45"|5
|width="45"|6
|width="45"|7
|width="45"|8
|width="45"|9
|width="45"|10
|width="45"|11
|-
|Последовательность a
|<tex>\$ \#_{start} a \$</tex>
|<tex>a</tex>
|<tex>b</tex>
|<tex>\$</tex>
|<tex>b \#_{start}</tex>
|<tex>\#_{yes} b</tex>
|<tex>\#_{yes}</tex>
|<tex>\#_{yes}</tex>
|<tex>\#_{yes}</tex>
|<tex>\#_{yes}</tex>
|<tex>\$ \$</tex>
|-
|Последовательность b
|<tex>\$</tex>
|<tex>a</tex>
|<tex>b</tex>
|<tex>\$</tex>
|<tex>\#_{start} a</tex>
|<tex>\#_{start} b</tex>
|<tex>a \#_{yes}</tex>
|<tex>b \#_{yes}</tex>
|<tex>\#_{yes} a</tex>
|<tex>\#_{yes} b</tex>
|<tex>\#_{yes} \$ \$</tex>
|}
{{Теорема
