Изменения

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

Навигация