Изменения
→Эквивалентность двухстековой машины трёхсчётчикой машине
*'''Снять символ со стека'''. Для того, чтобы снять символ, необходимо разделить число, которым представлен стек, на <tex>P</tex>, отбросив остаток. Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на <tex>P</tex>, и, если это удалось сделать, третий увеличивать на один. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый: пока третий счётчик не равен нулю, уменьшаем третий счётчик и увеличиваем первый.
*'''Добавить символ в стек'''. Для того, чтобы добавить символ, необходимо умножить число, которым представлен стек, на <tex>P</tex> и прибавить к нему номер символа, который добавляется на стек. Пусть символ добавляется в первый стек. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на один и увеличивать третий на <tex>P</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый.
* '''Проверка верхнего символа стека'''. Для этого необходимо найти остаток от деления на <tex>P</tex>. Скопируем значение первого счётчика на третий. Реализуем деление с остатком при При помощи введения дополнительных автоматовконечного автомата можно хранить целое число, входящих в управляющий автомат трехсчётчиковой машиныпринадлежащее конечному интервалу (каждое состояние автомата соответствует некоторому значению числа). Этот автомат должен состоять из Будем хранить остаток от деления третьего счётчика на <tex>P</tex> состояний. Каждое состояние соответствует определенному остатку от деленияИзначально инициализируем хранимое значение нулём. В случае, если Пока третий счётчик счетчик не нульбудем увеличивать по модулю <tex>P</tex> хранимое значение. Ясно, что когда третий счетчик станет равным нулю, запоминающий автомат осуществляет переход будет находится в состояниесостоянии, соответствующее следующему соответствующем остатку от деления. Если третий счётчик нуль, то остаток найден и осуществляется переход в управляющем автомате, соответствующий от деления. Будем уменьшать третий счетчик, каждый раз переходя в следующее состояние автомата.
<tex>\Leftarrow</tex>
