Gramatyka bezkontekstowa i PDA

Jeśli gramatyka G jest bezkontekstowy, możemy zbudować równoważny niedeterministyczny PDA, który akceptuje język, który jest tworzony przez gramatykę bezkontekstową G. Dla gramatyki można zbudować parserG.

Także jeśli P jest automatem przesuwającym w dół, można skonstruować równoważną gramatykę bezkontekstową G, gdzie

L(G) = L(P)

W następnych dwóch tematach omówimy, jak konwertować z PDA do CFG i odwrotnie.

Algorytm znajdowania PDA odpowiadającego danemu CFG

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

Output- Równoważne PDA, P = (Q, ∑, S, δ, q ₀ , I, F)

Step 1 - Zamień produkcje CFG na GNF.

Step 2 - PDA będzie miał tylko jeden stan {q}.

Step 3 - Symbol startu CFG będzie symbolem startu w PDA.

Step 4 - Wszystkie nieterminale CFG będą symbolami stosu PDA, a wszystkie terminale CFG będą symbolami wejściowymi PDA.

Step 5 - Do każdej produkcji w formie A → aX gdzie a jest terminalem i A, X są kombinacją terminali i nieterminali, wykonaj przejście δ (q, a, A).

Problem

Skonstruuj PDA na podstawie poniższego CFG.

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

gdzie są produkcje -

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

Rozwiązanie

Niech równoważny PDA,

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

gdzie δ -

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

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

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

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

Algorytm znajdowania CFG odpowiadającego danemu PDA

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

Output- Równoważne PDA, P = (Q, ∑, S, δ, q ₀ , I, F) takie, że nieterminalami gramatyki G będą {X _wx | W, X ∈ P} i stanu początkowego będzie _{Q0, M} .

Step 1- Dla każdego w, x, y, z ∈ Q, m ∈ S i a, b ∈ ∑, jeśli δ (w, a, ε) zawiera (y, m) i (z, b, m) zawiera (x, ε), dodaj regułę produkcji X _wx → a X _yz b w gramatyce G.

Step 2- Dla każdego w, x, y, z ∈ Q dodaj regułę produkcji X _wx → X _wy X _yx w gramatyce G.

Step 3- Dla w ∈ Q dodaj regułę produkcji X _ww → ε w gramatyce G.