Автомат с магазинной памятью

Описание: Формальное определение диаграмма автомата с магазинной памятью В отличие от конечных автоматов автомат с магазинной памятью является набором: где K конечное множество состояний автомата единственно допустимое начальное состояние автомата множество конечных состояний причём допустимо F=Ø и F=K Σ допустимый входной алфавит из которого формируются строки считываемые автоматом S алфавит памяти магазина нулевой символ памяти. Реализация автоматов с магазинной памятью отличается от конечных автоматов тем что текущее...

Дата добавления: 2014-08-04

Размер файла: 60.73 KB

Работу скачали: 59 чел.

Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск

В теории автоматов, автомат с магазинной памятью — это конечный автомат, который использует стек для хранения состояний.

Формальное определение

диаграмма автомата с магазинной памятью

В отличие от конечных автоматов, автомат с магазинной памятью является набором:

где

•  K — конечное множество состояний автомата
•  — единственно допустимое начальное состояние автомата
•  — множество конечных состояний, причём допустимо F=Ø, и F=K
•  Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом
•  S — алфавит памяти (магазина)
•  — нулевой символ памяти.

Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением . То есть, по комбинации текущего состояния, входного символа и символа на вершине магазина автомат выбирает следующее состояние и, возможно, символ для записи в магазин. В случае, когда в правой части автоматного правила присутствует e, в магазин ничего не добавляется, а элемент с вершины стирается. Если магазин пуст, то срабатывают правила с e в левой части.

Автомат с магазинной памятью может распознать любой контекстно-свободный язык.

В чистом виде автоматы с магазинной памятью используются крайне редко. Обычно это модель используется для наглядного представления отличия обычных конечных автоматов от синтаксических грамматик. Реализация автоматов с магазинной памятью отличается от конечных автоматов тем, что текущее состояние автомата сильно зависит от любого предыдущего.

until X=$ /* магазин пуст */

Виды автоматов с магазинной памятью

Существуют детерминированные и недетерминированные автоматы с магазинной памятью.

Для недетерминированных автоматов (в отличие от детерминированных) существует два эквивалентных критерия завершения работы:

1.  пустой магазин
2.  достижение конечного состояния

Детерминированный автомат завершает работу лишь тогда, когда достигает конечного состояния.

Определение 3.8. МП-автомат можно представить в виде семерки:

,                                               (3.11)

где Q – конечное множество состояний автомата;

      T – конечный входной алфавит;

      N – конечный магазинный алфавит;

      F – магазинная функция, отображающая множество

во множество всех подмножеств множества , т.е. F:;

      q0 – начальное состояние автомата, q0 Q;

      N0– начальный символ магазина, N0  N;

      Z –  множество заключительных состояний автомата, Z  Q.

Определение 3.9. Конфигурацией МП-автомата называется тройка вида: ,

где q - текущее состояние автомата, q  Q;

 - часть входной строки, первый символ которой находится под входной головкой,

- содержимое магазина,

Общая схема МП-автомата представлена на рисунке 3.3.

Алгоритм 3.8. Функционирование МП-автомата.

Начальной конфигурацией МП-автомата является конфигурация           (q0, , N0).

Шаг работы МП-автомата будем представлять в виде отношения непосредственного следования конфигураций (обозначается «|=») и отношения достижимости конфигураций (обозначается «|=*»). Если одним из значений магазинной функции  является , то записывается . При этом возможны следующие варианты.

1) Случай t  T. Автомат находится в текущем состоянии q, читает входной символ t, имеет в вершине стека символ S. Он переходит в очередное состояние q’, сдвигает входную головку на ячейку вправо и заменяет верхний символ S строкой магазинных символов. Вариант  означает, что S удаляется из стека.

2) Случай . Отличается от первого случая тем, что входной символ t просто не принимается во внимание, и входная головка не сдвигается. Такой шаг работы МП-автомата называется -шагом, который может выполняться даже после завершения чтения входной строки.

Заключительной конфигурацией МП-автомата является конфигурация   (q, , ), где q  Z.

Определение 3.10. МП-автомат допускает входную стоку , если существует путь по конфигурациям для некоторых q  Z и .

Определение 3.11. Язык L, распознаваемый (принимаемый) МП-автоматом М, определяется как множество вида:

и  для некоторых q  Z и }.