Изменения

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

Навигация