Эквивалентность магазинных автоматов и КС-грамматик

Теорема: Пусть G - КС-грамматика вида (V, N, S₀, P), по грамматике G можно построить магазинный автомат М такой, что L(G)=L(M).

Автомат М строится следующим образом: М= ({q}, V, NÈV, d, q, S₀, q)

1) Если в грамматике имеется правило A®a, то d(q, e, A)|- (q, a).

2) d(q, a, a)|- (q, e), "aÎV.

Пример:

G₀: E®E+T|T V= {(,), +, *, a}

T®T*F|F N= {E, T, F}

F® (E)| a

Построим автомат, соответствующий этой грамматике:

M= ({q}, V, NÈV, d, q, E, q)

d(q, e, E)|- {(q, E+T), (q, T)}

d(q, e, T)|- {(q, T*F), (q, F)}

d(q, e, F)|- {(q, (E)), (q, a)}

d(q, (, ()|- (q, e)

d(q,),))|- (q, e)

d(q, +, +)|- (q, e)

d(q, *, *)|- (q, e)

d(q, a, a)|- (q, e)

Рассмотрим цепочку a+a*a

(q, a+a*a, E) |- (q, a+a*a, E+T) |- (q, a+a*a, T+T) |- (q, a+a*a, F+T) |- (q, a+a*a, a+T) |- (q, +a*a, +T) |- (q, a*a, T) |- (q, a*a, T*F) |- (q, a*a, F*F) |- (q, a*a, a*F) |- (q, *a, *F) |- (q, a, F) |- (q, a, a) |- (q, e, e).

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

Утверждение 1: Любой регулярный язык является детерминированным. Обратное неверно.

Утверждение 2: Любой детерминированный язык является КС-языком. Обратное неверно.