Изменения

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

Навигация