PDA e grammatica senza contesto

Se una grammatica G è context-free, possiamo costruire un PDA non deterministico equivalente che accetta il linguaggio prodotto dalla grammatica context-free G. È possibile creare un parser per la grammaticaG.

Inoltre, se P è un automa pushdown, una grammatica libera dal contesto equivalente può essere costruita dove

L(G) = L(P)

Nei prossimi due argomenti, discuteremo come convertire da PDA a CFG e viceversa.

Algoritmo per trovare PDA corrispondente a un dato CFG

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

Output- Equivalente PDA, P = (Q, ∑, S, δ, q ₀ , I, F)

Step 1 - Converti le produzioni del CFG in GNF.

Step 2 - Il PDA avrà un solo stato {q}.

Step 3 - Il simbolo di inizio di CFG sarà il simbolo di inizio nel PDA.

Step 4 - Tutti i non terminali del CFG saranno i simboli dello stack del PDA e tutti i terminali del CFG saranno i simboli di input del PDA.

Step 5 - Per ogni produzione nella forma A → aX dove a è terminale e A, X sono una combinazione di terminali e non terminali, effettuare una transizione δ (q, a, A).

Problema

Costruisci un PDA dal seguente CFG.

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

dove sono le produzioni -

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

Soluzione

Lascia che l'equivalente PDA,

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

dove δ -

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

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

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

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

Algoritmo per trovare CFG corrispondente a un dato PDA

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

Output- Equivalente PDA, P = (Q, ∑, S, δ, q ₀ , I, F) tale che i non terminali della grammatica G saranno {X _wx | w, x ∈ Q} e lo stato di avvio sarà un _{q0, F} .

Step 1- Per ogni w, x, y, z ∈ Q, m ∈ S e a, b ∈ ∑, se δ (w, a, ε) contiene (y, m) e (z, b, m) contiene (x, ε), aggiungi la regola di produzione X _wx → a X _yz b nella grammatica G.

Step 2- Per ogni w, x, y, z ∈ Q, aggiungi la regola di produzione X _wx → X _wy X _yx nella grammatica G.

Step 3- Per w ∈ Q, aggiungi la regola di produzione X _ww → ε nella grammatica G.