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

КС-языки можно распознавать с помощью автомата с магазинной памятью (МП-автомата).

 

3.3.1 Определение МП-автомата

 

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

,

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

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

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

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

во множество всех подмножеств множества , т.е.

® ;

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

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

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

 

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

,

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

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

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

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

 

 
 

 


Рисунок 3.1 – Схема МП-автомата

 

 

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

 

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

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

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

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

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

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

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

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

 

3.3.2 Разновидности МП-автоматов

 

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

ПримерМП-автомат ,где

Q= {А} Т= {(,)}, N= {I,0}, qo = A, N0 = I,

F={ F(A,(,I)=(A,OI)

F(A,(,O)=(A,OO)

F(A,),O)=(A, )

F(A, ,I)=(A, )}

при распознавании строки (()()) строит последовательность конфигураций: (А, (() ()), I) |- (А, () () ), 01) |- (А,) ()), OOI) |- (А, ()), OI) |- (A,)), OOI) |- (А, ),О1) |- (А, , I) |- (А, , ).

Язык, принимаемый МП-автоматом в данном примере, это КС-язык парных круглых скобок. Этот же язык генерирует КС-грамматика с правилами Р = {S ->(S), S-> SS, S -> }.

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

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

МП-автомат называют детерминированным (ДМП-автоматом), если, находясь в любой конфигурации, он может выбрать не более одной следующей конфигурации. Это означает, что при любых значениях q Q, а (T { }) и N0 N |N0 N* (для расши­ренного автомата) магазинная функция (q, a, Z) имеет не более одного значения. В противном случае МП-автомат является не­детерминированным.

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

 

3.3.3 Взаимосвязь МП-автоматов и КС-грамматик

 

3.3.3.1 Построение МП-автомата по КС-грамматике

 

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

 

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

Выход: МП-автомат такой, что L(M) = L(G).

Шаг 1. Положить Q = {q}, q0 = q, Z = Æ, N = VT È VN, T = VT, N0 = S.

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

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

 

Пример Дана КС-грамматика:

G({+, (, ), a}, {S, A}, {S®S+A | A, A®(S) | a},{S}). Последовательность построения МП-автомата будет иметь вид.

1) Q = {q}, q0 = q, T = {+, (, ), a }, N = {+, (, ), a, S, A}, N0 = S, Z = Æ.

2) F(q, , S) = (q, S+A), F(q, , S) = (q, A), F(q, , A) = (q,(S)); F(q, , A) = (q, a).

3) F(q, t, t) = (q, ) для каждого t Î{+, (, ), a}.

 

Распознавание строки (а) построенным МП-автоматом представлено в таблице 3.1. Полученный МП-автомат является недетерминированным.

 

Таблица 3.1 – Распознавание МП-автоматом строки (а)

 

Номер конфигурации Текущее состояние Входная строка Содержимое магазина
q (a) S
q (a) A
q (a) (S)
q a) S)
q a) A)
q a) a)
q ) )
q

 

3.3.3.2 Построение расширенного МП-автомата по КС-грамматике

 

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

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

Выход: расширенный МП-автомат такой, что L(M) = L(G).

 

Шаг 1. Положить Q = {q, r}, q0 = q, Z = {r}, N = VT È VN È {#}, T = VT, N0 = #.

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

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

Шаг 4. Предусмотреть магазинную функцию для перевода автомата в заключительное состояние .

Пример Для грамматики из предыдущего примера построить расширенный МП-автомат. Последовательность построения МП-автомата будет иметь вид.

1) Q = {q, r}, q0 = q, T = {+, (, ), a}, N = {+, (, ), a, S, A}, N0 = #, Z = r.

2) F(q, , S+A) = (q, S), F(q, , A) = (q, S), F(q, , (S)) = (q, A), F(q, , a) =(q, A).

3) F(q, t, ) = (q, t) для каждого t Î{+, (, ), a}.

4) F(q, , #S) = (r, ).

Распознавание строки (а) расширенным МП-автоматом представлено в таблице 3.2. Полученный МП-автомат является детерминированным.

 

Таблица 3.2 – Распознавание расширенным МП-автоматом строки (а)

 

Номер конфигурации Текущее состояние Входная строка Содержимое магазина
q (a) #
q a) #(
q ) #(a
q ) #(A
q ) #(S
q #(S)
q #A
q #S
r







Дата добавления: 2016-03-27; просмотров: 3109;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.025 сек.