Работа магазинного автомата
Чтобы описать как работает автомат, введем понятие конфигурации.
| Определение. Конфигурацией автомата М называют тройку (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 ).
Пред.Страница
След.Страница Раздел Содержание
