КПК и контекстно-свободная грамматика

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

Кроме того, если P является автоматом выталкивания, эквивалентную контекстно-свободную грамматику G можно построить, где

L(G) = L(P)

В следующих двух темах мы обсудим, как конвертировать из КПК в CFG и наоборот.

Алгоритм поиска КПК, соответствующего заданному CFG

Input - А CFG, G = (V, T, P, S)

Output- Эквивалент КПК, P = (Q, ∑, S, δ, q 0 , I, F)

Step 1 - Преобразуйте продукцию CFG в GNF.

Step 2 - КПК будет иметь только одно состояние {q}.

Step 3 - Начальный символ CFG будет стартовым символом в КПК.

Step 4 - Все нетерминалы CFG будут символами стека КПК, а все терминалы CFG будут входными символами КПК.

Step 5 - Для каждой продукции в форме A → aX где a - терминал и A, X являются комбинацией терминального и нетерминального, сделайте переход δ (q, a, A).

Проблема

Создайте КПК из следующего CFG.

G = ({S, X}, {a, b}, P, S)

где производство -

S → XS | ε , A → aXb | Ab | ab

Решение

Пусть эквивалентный КПК,

P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)

где δ -

δ (q, ε, S) = {(q, XS), (q, ε)}

δ (q, ε, X) = {(q, aXb), (q, Xb), (q, ab)}

δ (q, a, a) = {(q, ε)}

δ (q, 1, 1) = {(q, ε)}

Алгоритм поиска CFG, соответствующего данному КПК

Input - А CFG, G = (V, T, P, S)

Output- Эквивалентный КПК, P = (Q, ∑, S, δ, q 0 , I, F) такой, что нетерминалы грамматики G будут {X wx | W, X ∈ Q} и начальное состояние будет q0, F .

Step 1- Для любых w, x, y, z ∈ Q, m ∈ S и a, b ∈ ∑, если δ (w, a, ε) содержит (y, m) и (z, b, m) содержит (x, ε) добавьте правило продукции X wx → a X yz b в грамматику G.

Step 2- Для каждого w, x, y, z ∈ Q добавьте правило продукции X wx → X wy X yx в грамматику G.

Step 3- Для w ∈ Q добавьте правило продукции X ww → ε в грамматику G.