Связь между КС-языками и недетерминированными автоматами выража­ются теоремами, которые показывают, что класс языков, допускаемых мага­зинными автоматами при пустом магазине, есть в точности класс КС-языков.

Теорема 3.2.1. [4] Пусть L(G) — КС-язык, порождаемый грамматикой G = <N, T, P, S> в нормальной форме Грейбах. Тогда существует недетерминированный нисходящий МП-автомат М, такой, что он допускает все слова языка L(G) и только их, причем автомат М = <A, Q, Г, , q₀, Z₀, F> строится следующим образом:

1) A = T;

2) Q = {q₁};

3) Г = N;

4) q₀ = q₁;

5) Z₀ = S;

6) F =;

7) (q₁, )(q₁, a, B) всегда, когда подстановка Ba принадлежит множеству правил Р грамматики G, здесь BN, aT, {NT}*.

Теорема 3.2.2. [4] Пусть L(M) — язык, допускаемый магазинным автоматом М = <A, Q, Г, , q₀, Z₀, F>. Тогда существует такая КС-грамматика G = <N, T, P, S>, что L(G)=L(M),

1) где T =A;

2) N — множество вида (q, B, p), q, p Q и ВГ;

3) подстановка S(q₀, z₀, q) принадлежит множеству правил Р при любом qQ;

4) подстановки (q, B, p)(q₁, B₁, q₂) (q₂, B₂, q₃) … (q_m, B_m, q_m+1) принадлежат множеству Р для всех q, q₁, q₂, …,q_m+1Q, p = q_m+1, для любого a{A{}} и любых B, B₁, B₂, …, B_m  Г таких, что (q₁, B₁B₂…B_m)(q, a, B). Если же m = 0, то q₁ = p, p(q, a, B) и (q, B, p)  а принадлежит множеству Р.

Пример 3.2.1. [14]. Дана КС-грамматика G = <N, T, P, S>, у которой

N = {S, D, B}, T = {a, b},

  P = {    S  aB

              S  bD

              D aS

              D a

              D bDD

              B aBB

              B bS

              B b}

В соответствии с теоремой 3.2.1 МП-автомат М = <A, Q, Г, , q₀, Z₀, F>, допускающий данный КС-язык, будет включать в себя компоненты A = {a, b}, Q = {q₁},       Г = {S, D, B}, q₀=q₁, z₀=S  и отображение , заданное в виде:

1) (q₁, a, S)  (q₁, B),                                     т.к. (SaB)P;

2) (q₁, b, S)  (q₁, D),                                    т.к. (SbD)P;

3) (q₁, a, D)  {(q₁, S), (q₁, )},                   т.к. (DaS) и (Da)

входят во множество P;

4) (q₁, b, D)  (q₁, DD),                                 т.к. (DbDD)P;

5) (q₁, a, B)  (q₁, BB),                                  т.к. (BaBB)P;

6) (q₁, b, B)  {(q₁, S), (q₁, )},                   т.к. (BbS) и (Bb)

входят во множество P.

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