Пред.Страница
След.Страница
Раздел
Содержание
2.9
Работа магазинного автомата.
Чтобы описать как работает автомат, введем понятие конфигурации.
| Определение. Конфигурацией автомата
М называют тройку (s,
a , g )
О S
x P* x H* , |
где s - текущее состояние управляющего
устройства,
a -неиспользованная
часть входной цепочки a
О P* ,самый левый символ этой цепочки
a находится под головкой. Если a
=e , то считается, что входная цепочка
прочитана.
g -цепочка
, записанная в магазине, g
О H* ,самый правый символ цепочки
считается вершиной магазина. Если g=
$ , то магазин пуст.
Работа автомата может быть представлена как смена конфигураций. Один
такт работы автомата заключается в определении новой конфигурации по заданной.
Это записывается так:
( s, aa , g h ) |--
( s', a , gb )
При этом предполагается, что автомат читает символ a,
находящийся под головкой, и символ h,
находящийся в вершине магазина, определяет новое состояние s'
и записывает цепочку b
в
магазин вместо символа h. Если
b =$ , то
верхний символ оказывается удаленным из магазина.
Такая смена конфигураций возможна, если функция f(
s, a, h ) определена и ей принадлежит
значение ( s', b ).
Описанный такт работы выполняется с перемещением головки. Для описания
работы автомата нам потребуется другой вид такта, предполагающий изменение
состояний и магазина без перемещения входной головки. Если f0(s,
e, h) определена и ей принадлежит
значение (s', b )
, то он определяет смену конфигураций так:
( s, aa , g
h ) |-- ( s', aa , gb )
Таким образом, могут быть три случая при работе автомата:
-
f(s, a, h) определена и выполняется
такт работы,
-
f(s, a, h) не определена, но
определена функция f0(s,
e, h) и выполняется пустой такт.
-
Функции f(s, a, h) и f0(s,
e, h)
не определены, в этом случае дальнейшая работа автомата невозможна.
В общем виде действия, задаваемые функцией переходов и выполняемые автоматом,
демонстрирует следующая форма записи:
f(s, <входной символ>, <магазинный символ>)=(s1,
<заносимая цепочка>)
При этом следует иметь в виду, что при выполнении такта вначале читается
символ в вершине, а затем на его место заносится новый символ или цепочка.
Отдельные значения функции переходов часто называют командами магазинного
автомата.
Начальной конфигурацией называется
конфигурация (sо, a
, hо) , где sо
-начальное состояние и hо
- маркер дна магазина, а заключительной -
конфигурация (s, $ , $) , где
s принадлежит множеству конечных состояний
F.
Для обозначения последовательности сменяющих друг друга конфигураций
условимся
использовать знак |--*. Таким образом последовательность
( s1, a 1, g
1 ) |-- ( s2, a 2,
g 2) |-- ...|-- ( sn,
a n,g
n )
записывается в сокращенном виде так:
(s1,a
1, g 1 ) |--* ( sn,
a n,g
n ).
Пред.Страница
След.Страница
Раздел
Содержание
