PDA e gramática livre de contexto

Se uma gramática G é livre de contexto, podemos construir um PDA não determinístico equivalente que aceita a linguagem que é produzida pela gramática livre de contexto G. Um analisador pode ser construído para a gramáticaG.

Também se P é um autômato pushdown, uma gramática livre de contexto equivalente G pode ser construída onde

L(G) = L(P)

Nos próximos dois tópicos, discutiremos como converter de PDA para CFG e vice-versa.

Algoritmo para encontrar PDA correspondente a um determinado CFG

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

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

Step 1 - Converter as produções do CFG em GNF.

Step 2 - O PDA terá apenas um estado {q}.

Step 3 - O símbolo de início de CFG será o símbolo de início no PDA.

Step 4 - Todos os não terminais do CFG serão os símbolos da pilha do PDA e todos os terminais do CFG serão os símbolos de entrada do PDA.

Step 5 - Para cada produção no formulário A → aX onde a é terminal e A, X são uma combinação de terminais e não terminais, faça uma transição δ (q, a, A).

Problema

Construa um PDA a partir do seguinte CFG.

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

onde as produções estão -

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

Solução

Deixe o PDA equivalente,

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

onde δ -

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

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

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

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

Algoritmo para encontrar CFG correspondente a um determinado PDA

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

Output- PDA equivalente, P = (Q, ∑, S, δ, q ₀ , I, F) tal que os não terminais da gramática G serão {X _wx | w, x ∈ Q} e o estado inicial será Um _{q0, F} .

Step 1- Para cada w, x, y, z ∈ Q, m ∈ S e a, b ∈ ∑, se δ (w, a, ε) contém (y, m) e (z, b, m) contém (x, ε), adicione a regra de produção X _wx → a X _yz b na gramática G.

Step 2- Para cada w, x, y, z ∈ Q, adicione a regra de produção X _wx → X _wy X _yx na gramática G.

Step 3- Para w ∈ Q, adicione a regra de produção X _ww → ε na gramática G.