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

Equivalencia de gramáticas

Sean G₁ y G₂ dos gramáticas con un mismo conjunto de símbolos terminales. Diremos que G₂ subsume a G₁ si toda palabra generada en G₁ es también generada en G₂, 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 s₀ en G₁, 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 G₂, entonces la concatenación de estas últimas derivaciones ha de dar una derivación de $\sigma$ a partir del símbolo inicial s₀ en G₂.


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

$$G_1\equiv G_2 \;\Leftrightarrow\; L(G_1)= L(G_2).$$

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.

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