next up previous contents
Siguiente: Ejemplos Un nivel arriba: Gramáticas formales Anterior: Elevación al cuadrado

Equivalencia de gramáticas

Sean G1 y G2 dos gramáticas con un mismo conjunto de símbolos terminales. Diremos que G2 subsume a G1 si toda palabra generada en G1 es también generada en G2, es decir, si $L(G_1)\subset L(G_2)$. Escribiremos en este caso $G_1\leq G_2$.

Proposición 3.1   La relación de subsunción es una relación reflexiva y transitiva en la clase de gramáticas con un alfabeto terminal fijo.

La subsunción no es antisimétrica pues dos gramáticas distintas pueden generar a un mismo lenguaje. Una condición suficiente, mas no necesaria, para revisar si acaso una gramática queda subsumida por otra la da la siguiente

Observación 3.1   Sean $G_1=\left(V,T, P_1,s_{0}\right)$ y $G_2=\left(V,T, P_2,s_{0}\right)$ dos gramáticas con un mismo alfabeto. Si para cada producción $(\alpha,\beta)\in P_1$ se tiene que $G_2\vdash(\alpha\rightarrow \beta)$, entonces $G_1\leq G_2$.

Y, en efecto, si $\sigma\in L(G_1)$ y $\sigma_0P_{i_1}\sigma_1\cdots \sigma_{k-1}P_{i_k}\sigma_{k}$ es una derivación de $\sigma$ a partir del símbolo inicial s0 en G1, y para cada j, $\sigma_{j}$ se deriva de $\sigma_{j-1}$ mediante una derivación $\tau_{j0}Q_{j_1}\tau_{j1}\cdots \tau_{j,k_j-1}Q_{j_{k_j}}\tau_{j,k_j}$ en G2, entonces la concatenación de estas últimas derivaciones ha de dar una derivación de $\sigma$ a partir del símbolo inicial s0 en G2.


Dos gramáticas son equivalentes si cualquiera de ellas subsume a la otra, es decir,

\begin{displaymath}G_1\equiv G_2 \;\Leftrightarrow\; L(G_1)= L(G_2).\end{displaymath}

La relación de equivalencia es, efectivamente, una relación de equivalencia en la clase de gramáticas con un alfabeto terminal fijo. La relación de subsunción es en efecto una relación de orden en el cociente de las gramáticas con un mismo conjunto de símbolos terminales partido por la relación de equivalencia.

 
next up previous contents
Siguiente: Ejemplos Un nivel arriba: Gramáticas formales Anterior: Elevación al cuadrado
Guillermo Morales-Luna
2000-06-27