Главная | Обратная связь
МегаЛекции

Пункт 1. Определение МП-автомата.





Подобно тому, как регулярные языки можно распознавать конечным автоматом, КС-языки можно распознавать с помощью автомата с магазинной памятью, или МП-автомата. Последний эквивалентен конечному автомату, который снабжен рабочей памятью магазинного типа, то есть стеком.

МП-автомат читает входной символ, замещает верхний символ стека строкой символов и переходит в новое состояние. Новое состояние определяется прочитанным символом и содержимым вершины стека. МП-автомат принимает строку, если после ее прочтения автомат находится в заключительном состоянии.

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

, где

- конечное множество состояний автомата;

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

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

- магазинная функция, отображение множества в множество всех подмножеств множества

;

- начальное состояние автомата, ;

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

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

 

Конфигурацией МП-автомата называется тройка

где

- текущее состояние автомата;

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

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

 

Шаг работы МП-автомата представим в виде отношения |- на конфигурациях. Если одним из значений магазинной функции является , то можно писать . Это общая запись, которая подразумевает частные случаи.

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

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

 



Начальной конфигурацией МП-автомата называется конфигурация , а заключительной – конфигурация , где . В заключительном состоянии входная строка полностью прочитана. Таким образом, МП-автомат допускает входную строку , если существует путь по конфигурациям

для некоторых и . Значит, язык , распознаваемый (принимаемый) МП-автоматом , формально можно определить так:

.

 

 

Пункт 2. Разновидности МП-автоматов.

Иногда определяют МП-автомат, который принимает строку, если после завершения ее чтения стек автомата будет пуст. В этом случае нет необходимости выделять множество заключительных состояний , а описание заключительной конфигурации имеет вид , где . Говорят, что такой МП-автомат принимает строку языка опустошением магазина.

МП-автомат называют детерминированным (ДМП-автоматом), если, находясь в любой конфигурации, он может выбрать не более одной следующей конфигурации. Это означает, что при любых значениях , и ( для расширенного автомата) магазинная функция имеет не более одного значения. В противном случае МП-автомат является недетерминированным.

Существует соответствие КС-грамматик и МП-автоматов, которое можно сформулировать так: существуют КС-языки, МП-автоматы и расширенные МП-автоматы, определяющие один и тот же КС-язык.

 

Пункт 3. Взаимосвязь МП-автоматов и КС-грамматик.

Построение МП-автомата.

По заданной КС-грамматике, генерирующей некоторый язык , можно построить МП-автомат, принимающий этот язык. Будем строить автомат, выполняющий левосторонний разбор. Такой автомат должен строить вывод строки, начиная с аксиомы грамматики. Используем стек для размещения текущей сентенциальной формы, первоначально это аксиома. Очередная сентенциальная форма получается заменой верхнего нетерминала стека. Пусть, кроме того, автомат обладает только одним состоянием и принимает входную строку опустошением магазина. Описанный МП-автомат можно построить следующим образом.

Вход: КС-грамматика .

Выход: МП-автомат такой, что .

1. Положить

2. Для каждого правила вида , где , сформировать магазинную функцию вида . Эти функции предписывают замещать нетерминал в вершине стека по правилу грамматики.

3. Для каждого сформировать магазинную функцию вида , которая выталкивает из стека символ, совпадающий с входным, и перемещает читающую головку. Эти функции обеспечивают опустошение стека.

 





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2020 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.