PDA y gramática libre de contexto
Si una gramática G es libre de contexto, podemos construir un PDA no determinista equivalente que acepte el lenguaje producido por la gramática libre de contexto G. Se puede construir un analizador para la gramáticaG.
También si P es un autómata pushdown, se puede construir una gramática libre de contexto equivalente G donde
L(G) = L(P)
En los siguientes dos temas, discutiremos cómo convertir de PDA a CFG y viceversa.
Algoritmo para encontrar PDA correspondiente a un CFG dado
Input - Un CFG, G = (V, T, P, S)
Output- PDA equivalente, P = (Q, ∑, S, δ, q 0 , I, F)
Step 1 - Convertir las producciones del CFG en GNF.
Step 2 - La PDA tendrá un solo estado {q}.
Step 3 - El símbolo de inicio de CFG será el símbolo de inicio en la PDA.
Step 4 - Todos los no terminales del CFG serán los símbolos de pila del PDA y todos los terminales del CFG serán los símbolos de entrada del PDA.
Step 5 - Para cada producción en forma A → aX donde a es terminal y A, X son una combinación de terminales y no terminales, haga una transición δ (q, a, A).
Problema
Construya un PDA a partir del siguiente CFG.
G = ({S, X}, {a, b}, P, S)
donde están las producciones -
S → XS | ε , A → aXb | Ab | ab
Solución
Deje que el PDA equivalente,
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
donde δ -
δ (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 correspondiente a un PDA dado
Input - Un CFG, G = (V, T, P, S)
Output- PDA equivalente, P = (Q, ∑, S, δ, q 0 , I, F) tal que los no terminales de la gramática G serán {X wx | w, x ∈ Q} y el estado de inicio será un q0, F .
Step 1- Para cada w, x, y, z ∈ Q, m ∈ S y a, b ∈ ∑, si δ (w, a, ε) contiene (y, m) y (z, b, m) contiene (x, ε), agregue la regla de producción X wx → a X yz b en la gramática G.
Step 2- Para cada w, x, y, z ∈ Q, agregue la regla de producción X wx → X wy X yx en la gramática G.
Step 3- Para w ∈ Q, agregue la regla de producción X ww → ε en la gramática G.