Изменения

# Запускаем <tex> M </tex> на слове, находящемся в буфферебуфере. # После того, как <tex> M </tex> обработал весь буффербуфер, переходим к пункту 2.

Пусть в автомате <tex> M </tex> было <tex> n </tex> состояний. Для того, чтобы научиться сохранять слова в буфферебуфере, создадим <tex> |\Sigma|^{k+1} n </tex> дополнительных состояний в новом автомате, где <tex> k = \max\limits_{c \in \Sigma} | h(c) | </tex>. Это позволит в состоянии кодировать слово, которое находится сейчас в буфферебуфере. Переходы в этих состояниях совершаются на основе того, что стоит на первом месте в буфферебуфере, состояния автомата и вершины стека. На ленту переходы в этих состояниях не смотрят. Из состояния, в котором буффер буфер пуст, добавим <tex> \varepsilon </tex>-переход в начальное состояние. Необходима картинка.