PDA y gramática libre de contexto
AREAtutorial » Tutoriales de IngenierÃa » PDA y gramática libre de contexto
Si gramatica gramo es independiente del contexto, podemos construir un PDA no determinista equivalente que acepte un lenguaje creado con una gramática libre de contexto gramo… El analizador se puede construir para gramática gramo…
Además, si PAG es un autómata de extrusión, 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 PDA a CFG y viceversa.
aporte – Un CFG, G = (V, T, P, S)
Salida – CPC equivalente, P = (Q, ∑, S, δ, q0, I, F)
Paso 1 – Conversión de productos CFG a GNF.
Paso 2 – La PDA tendrá un solo estado {q}.
Paso 3 – El sÃmbolo de inicio CFG será el sÃmbolo de inicio en la PDA.
Paso 4 – Todos los terminales que no sean CFG serán caracteres de pila de PDA y todos los terminales CFG serán caracteres de entrada de PDA.
Paso 5 – Para cada producto en el formulario A → aX donde a es la terminal y A, X son una combinación de terminal y no terminal, da el salto δ (q, a, A)…
Construya una PDA a partir del siguiente CFG.
G = ({S, X}, {a, b}, P, S)
donde la producción –
S → XS | ε, A → aXb | Ab | ab
Deje que el CPC 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, ε)}
aporte – Un CFG, G = (V, T, P, S)
Salida – Un CPC equivalente, P = (Q, ∑, S, δ, q0, I, F) tal que los no terminales de la gramática G son {Xwx | w, x ∈ Q} y el estado inicial será Aq0, F.
Paso 1 – Para cualquier 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 Xwx → a Xyzb a la gramática G.
Paso 2 – Para cada w, x, y, z ∈ Q agregue la regla de producción Xwx → XwyXyx a la gramática G.
Paso 3 – Para w ∈ Q agregue la regla de producción Xww → ε a la gramática G.
🚫