КС-грамматики и МП-автоматы

Пусть G = (N, T, P, S) - контекстно-свободная грамматика. Введем несколько важных понятий и определений.

Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S

*u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определяется правосторонний вывод. Будем обозначать шаги левого (правого) вывода посредством l (r).

Упорядоченным

графом называется пара (V, E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), ..., (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй - дуга, входящая в вершину v2, и т.д.

Упорядоченным помеченным деревом называется упорядоченный граф (V, E), основой которого является дерево и для которого определена функция f : V

F (функция

разметки) для некоторого множества F.

Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:

корень дерева D помечен S;

каждый лист помечен либо a

T, либо e;

каждая внутренняя вершина помечена нетерминалом A

N;

если X - нетерминал, которым помечена внутренняя вершина и X1, ..., Xn - метки ее прямых потомков в указанном порядке, то

X

X1...Xk - правило из множества P;

Цепочка, составленная из выписанных слева направо меток листьев, равна w.

Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.

Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A

+A для некоторой цепочки .

Автомат с магазинной памятью (МП-автомат) - это семерка M = (Q, T,

, D, q0, Z0, F), где

Q - конечное множество состояний,

представляющих всевозможные состояния управляющего устройства;

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

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

D - отображение множества QЧ(T

{e})Ч

в множество конечных подмножеств QЧ

*, называемое функцией переходов;

q0

Q - начальное состояние управляющего устройства;

Z0

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

F

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

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

тройка (q, w, u), где

q

Q - текущее состояние управляющего устройства;

w

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

u

* - содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считается пустым.

Такт работы МП-автомата M будем представлять в виде бинарного отношения , определенного на конфигурациях. Будем писать

если множество D(q, a, Z) содержит (p, v), где q, p Q, a T {e}, w T*, Z и u, v *.

Начальной конфигурацией МП-автомата M называется конфигурация вида (q0, w, Z0), где w T*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине находится только начальный символ Z0.

Заключительная конфигурация - это конфигурация вида (q, e, u), где q F, u *, т.е. управляющее устройство находится

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

Введем транзитивное и рефлексивно-транзитивное замыкание отношения , а также его степень k 0 (обозначаемые +, * и k соответственно).

Говорят, что цепочка w допускается МП-автоматом M, если (q0, w, Z0) *(q, e, u) для некоторых q F и u *.

Язык, допускаемый (распознаваемый, определяемый) автоматомM (обозначается L(M)) - это множество всех цепочек, допускаемых автоматом M.

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



у которого функция переходов D содержит следующие элементы:

 

D(q0, a, Z) = {(q0, aZ)},

D(q0, b, Z) = {(q0, bZ)},

D(q0, a, a) = {(q0, aa), {q1, e)},

D(q0, a, b) = {(q0, ab)},

D(q0, b, a) = {(q0, ba)},

D(q0, b, b) = {(q0, bb), (q1, e)},



D(q1, a, a) = {(q1, e)},

D(q1, b, b) = {(q1, e)},

D(q1, e, Z) = {(q2, e)}.

 

Нетрудно показать, что L(M) = {wwR|w {a, b}+}, где wR

обозначает обращение («переворачивание») цепочки w.

Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если (q0, w, Z0) *(q, e, e) для некоторого q Q. В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедлива

Теорема 4.1. Язык допускается магазинным автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом) опустошением магазина.

Доказательство. Пусть L = L(M) для некоторого МП-автомата M = (Q, T, , D, q0, Z0, F). Построим новый МП-автомат M', допускающий тот же язык опустошением магазина.

Пусть M' = (Q{q0', qe}, T, {Z0'}, D', q0', Z0', ), где функция переходов D' определена следующим образом:

Если (r, u)

D(q, a, Z), то (r, u)

D'(q, a, Z) для всех q

Q, a

T

{e} и Z

;

D'(q0', e, Z0') = {(q0, Z0Z0')};

Для всех q

F и Z

{Z0'} множество D'(q, e, Z) содержит (qe, e);

D'(qe, e, Z) = {(qe, e)} для всех Z

{Z0'}.

Автомат сначала переходит в конфигурацию (q0, w, Z0Z0') в соответствии с определением D' в п.2, затем в (q, e, Y 1...Y kZ0'), q F в соответствии с п.1, затем в (qe, e, Y 1...Y kZ0'), q F в соответствии с п.3, затем в (qe, e, e) в соответствии с п.4. Нетрудно показать по индукции, что (q0, w, Z0) +(q, e, u) (где q F) выполняется для автомата M тогда и только тогда, когда (q0', w, Z0') +(qe, e, e) выполняется для автомата M'. Поэтому L(M) = L', где L' - язык, допускаемый автоматом M' опустошением магазина.

 

Обратно, пусть M = (Q, T, , D, q0, Z0, ) - МП-автомат, допускающий опустошением магазина язык L.

Построим автомат M', допускающий тот же язык по заключительному состоянию.

Пусть M' = (Q{q0', qf}, T, {Z0}, D', q0', Z0', {qf}), где D' определяется следующим образом:

D'(q0', e, Z0') = {(q0, Z0Z0')} - переход в «режим M»;

Для каждого q

Q, a

T

{e}, и Z

определим D'(q, a, Z) = D(q, a, Z) - работа в «режиме M»;

Для всех q

Q, (qf, e)

D'(q, e, Z0') - переход в заключительное состояние.

Нетрудно показать по индукции, что L = L(M'). __

Одним из важнейших результатов теории контекстно-свободных языков является доказательство эквивалентности

МП-автоматов и КС-грамматик.

Теорема 4.2. Язык является контекстно-свободным тогда и только тогда, когда он допускается магазинным автоматом.

Доказательство. Пусть G = (N, T, P, S) - КС-грамматика. Построим МП-автомат M, допускающий язык L(G) опустошением магазина.

Пусть M = ({q}, T, N T, D, q, S, ), где D определяется следующим образом:

Если A

u

P, то (q, u)

D(q, e, A);

D(q, a, a) = {(q, e)} для всех a

T.

Фактически, этот МП-автомат в точности моделирует все возможные выводы в грамматике

G. Нетрудно показать по индукции, что для любой цепочки w T*

вывод S +w в грамматике G существует тогда и только тогда, когда существует последовательность тактов (q, w, S) +(q, e, e) автомата M.

 

Обратно, пусть M = (Q, T, , D, q0, Z0, ) - МП-автомат, допускающий опустошением магазина язык L. Построим грамматику G, порождающую язык L.

Пусть G = ({ [qZr] | q, r Q, Z }{S}, T, P, S), где P состоит из правил следующего вида:

• Если (r, X1...Xk)
  
  D(q, a, Z), k
  
  1, то
  
  
  
  для любого набора s1, s2, ..., sk состояний из Q;



• Если (r, e)
  
  D(q, a, Z), то [qZr]
  
  a
  
  P, a
  
  T
  
  {e};



• S
  
  [q0Z0q]
  
  P для всех q
  
  Q.

Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левосторонний вывод w в грамматике G.

Индукцией по числу шагов вывода в G или числу тактов M нетрудно показать, что (q, w, A) +(p, e, e) тогда и только тогда, когда [qAp] +w.

Тогда, если w L(G), то S [q0Z0q] +w для некоторого q Q. Следовательно, (q0, w, Z0) +(q, e, e) и поэтому

w L. Аналогично, если w L, то (q0, w, Z0) +(q, e, e). Значит, S [q0Z0q] +w, и поэтому w L(G). __

МП-автомат M = (Q, T, , D, q0, Z0, F) называется детерминированным (ДМП-автоматом), если выполнены следующие два условия:

Множество D(q, a, Z) содержит не более одного элемента для любых q

Q, a

T

{e}, Z

;

Если D(q, e, Z)

, то D(q, a, Z) =

для всех a

T.

Язык, допускаемый ДМП-автоматом, называется детерминированным КС-языком.

Так как функция переходов ДМП- автомата содержит не более одного элемента для любой тройки

аргументов, мы будем пользоваться записью D(q, a, Z) = (p, u) для обозначения D(q, a, Z) = {(p, u)}.

Пример 4.2. Рассмотрим ДМП-автомат



у которого функция переходов определяется следующим образом:

 

D(q0, X, Y ) = (q0, XY ), X {a, b}, Y {Z, a, b},

D(q0, c, Y ) = (q1, Y ), Y {a, b},

D(q1, X, X) = (q1, e), X {a, b},

D(q1, e, Z) = (q2, e).

 

Нетрудно показать, что этот детерминированный МП-автомат допускает язык L = {wcwR|w {a, b}+}.

К сожалению, ДМП-автоматы имеют меньшую распознавательную способность, чем МП-автоматы. Доказано, в частности, что

существуют КС-языки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).

Рассмотрим еще одну важную разновидность МП-автомата.

Расширенным автоматом с магазинной памятью назовем семерку M = (Q, T, , D, q0, Z0, F), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечного подмножества множества QЧ(T {e})Ч*

во множество конечных подмножеств множества QЧ*. Все остальные определения (конфигурации, такта, допустимости) для расширенного

МП-автомата остаются такими же, как для обычного.

Теорема 4.3. Пусть M = (Q, T, , D, q0, Z0, F) - расширенный МП-автомат. Тогда существует такой МП-автомат M', что L(M') = L(M).

Расширенный МП-автомат M = (Q, T, , D, q0, Z0, F) называется детерминированным, если выполнены следующие условия:

• Множество D(q, a, u) содержит не более одного элемента для любых q
  
  Q, a
  
  T
  
  {e}, Z
  
  
  *;



• Если D(q, a, u)
  
  
  , D(q, a, v)
  
  
  и u
  
  v, то не существует цепочки x такой, что u = vx или v = ux;



• Если D(q, a, u)
  
  
  , D(q, e, v)
  
  
  , то не существует цепочки x такой, что u = vx или v = ux.

Теорема 4.4. Пусть M = (Q, T, , D, q0, Z0, F) - расширенный ДМП-автомат. Тогда существует такой ДМП-автомат M', что L(M') = L(M).

ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе, соответственно, LL и LR-анализаторов.


Содержание раздела

---