Формальные языки


Работа магазинного автомата


Чтобы описать как работает автомат, введем понятие конфигурации.
 

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




  • - Начало -  - Назад -  - Вперед -