171
правка
Изменения
м
Нет описания правки
# <tex>q \rightarrow e</tex> для каждого <tex>q \in F</tex>
Используя правила 1 и 2 , <Br>,<tex>A_1 \Rightarrow^* q_o[a_1,a_1][a_2,a_2]...[a_n,a_n]A_2</tex>, где <tex>a_i \in \Sigma</tex> для некоторого <tex>i</tex>.
Предположим, что <tex>Tm</tex> допускает строку <tex>a_1a_2...a_n</tex>. Тогда для некоторого <tex>m</tex> <tex>Tm</tex> использует не более, чем <tex>m</tex> ячеек справа от входа. Используя правило 3, а затем правило 4 <tex>m</tex> раз, и, наконец, правило 5, имеем:<br>
