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 0 , 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 0 , 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.