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

Формальное определение диаграмма автомата с магазинной памятью В отличие от конечных автоматов автомат с магазинной памятью является набором: где 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 и }.



 

Другие похожие работы, которые могут вас заинтересовать.
15590. Автомат стыковой сварки 332.1 KB
  Исполнение по условному проходу 10 мм УХЛ – климатическое исполнение для районов с умеренным и холодным климатом; категория размещения; Дроссели 7 шт. Определение внутреннего диаметра трубопровода Внутренний диаметр трубопровода: - регламентированная скорость для напорных магистралей. - регламентированная скорость для сливных магистралей. Определение минимальной толщины стенок трубы для...
7630. Управление памятью 66.2 KB
  Иерархия памяти В настоящее время в ЭВМ сложилась трехуровневая организация памяти. По мере увеличения уровня памяти весьма существенным образом уменьшается время доступа к хранимым в ней данным и объем самой памяти а стоимость памяти в расчете на один бит информации сильно возрастает. Центральный процессор ЦП может непосредственно обращаться к ОП и кэшпамяти при этом в случае отсутствия данных в кэшпамяти но их наличии в ОП перепись их из ОП в кэшпамять происходит автоматически только с помощью аппаратных средств без участия...
2779. УПРАВЛЕНИЕ ПАМЯТЬЮ В ОС UNIX И WINDOWS 93.5 KB
  Напишите программу, которая будет сравнивать среднее время доступа к жесткому диску с включенным кэшированием записи и без него. Сравните и обоснуйте полученные результаты. Операционная система - Windows.
9093. Аппаратно-независимый уровень управления виртуальной памятью 49.28 KB
  Для обеспечения нужной производительности менеджер памяти ОС старается поддерживать в оперативной памяти актуальную информацию пытаясь угадать к каким логическим адресам последует обращение в недалеком будущем. Для обеспечения нужной производительности менеджер памяти ОС старается поддерживать в оперативной памяти актуальную информацию пытаясь угадать к каким логическим адресам последует обращение в недалеком будущем. Для каждой виртуальной страницы запись в таблице страниц содержит номер соответствующего страничного кадра в оперативной...
9094. Организация памяти компьютера. Простейшие схемы управления памятью 55.41 KB
  Программы вместе с данными к которым они имеют доступ в процессе выполнения должны по крайней мере частично находиться в оперативной памяти. Операционной системе приходится решать задачу распределения памяти между пользовательскими процессами и компонентами ОС. Часть ОС которая отвечает за управление памятью называется менеджером памяти.
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.