Siguiente: Tipos de gramáticas Un nivel arriba: Equivalencia de gramáticas Anterior: Equivalencia de gramáticas

Ejemplos

Palíndromas Sea $G_1=\left(\{s_0\},\{a,b\}, P_1,s_0\right)$ la gramática con producciones $s_0\rightarrow \mbox{\it nil\/}\vert as_0a\vert bs_0b$ Observamos que con la aplicación de cada regla,

se añade un par de símbolos, aquí iguales, o bien no se añade símbolo alguno, y el símbolo que se añade al inicio se ha de ``equilibrar'' con otro igual al final.

Así pues, es muy fácil ver que el lenguaje generado por esta gramática consta de los palíndromas de longitud par sobre (a+b),

$$L(G_1)=\{\sigma\in(a+b)^* \vert \mbox{\rm long}(\sigma)\equiv 0\mbox{\rm mod }2\ \&\ \mbox{\rm reverso}(\sigma)=\sigma\}.$$

Sea G₂ la gramática que coincide con G₁ salvo en que contiene además las producciones $s_0\rightarrow a\vert b$. Entonces G₂ genera a todos los palíndromas en (a+b)^*. G₂ subsume a la gramática G₁.


Cadenas equilibradas de paréntesis Recordamos que las cadenas equilibradas de paréntesis (CEP) quedan caracterizadas por las siguientes proposiciones: a) () es una CEP. b) Si E,F son dos CEP's entonces tanto (E) como EF son CEP's. c) Las CEP's son únicamente las cadenas obtenidas por las reglas anteriores. Así pues consideremos la gramática $G_1=\left(\{S\},\{(,)\},P_1,S\right)$, donde P₁ consta de las reglas

$$S\rightarrow ()\vert(S)\vert SS.$$

De acuerdo con las reglas descritas arriba, G₁ genera a las CEP's. Por ejemplo, una derivación de la cadena ()(()()) se muestra en la tabla (2.8-(a)).

  

Table 2.8: Ejemplo de una CEP generada en sendas gramáticas equivalentes. (Se indica con una flecha sobre cuál símbolo variable se aplica la regla indicada por el número de abajo.)

Consideremos ahora la gramática G₂ con símbolo inicial S y producciones

$$\begin{eqnarray*}s)\ \ S &\rightarrow& (A \\ a)\ \ A &\rightarrow& ) \vert )S \vert )(A \vert (AA \end{eqnarray*}$$

Esta gramática también genera a las cadenas equilibradas de paréntesis. Tan solo como un ejemplo, se muestra la derivación de la cadena anterior en la tabla (2.8-(b)). Para ver que G₁ subsume a G₂, es decir, que toda palabra terminal generada en G₂ es generada también en G₁, basta observar que para cualquier $\sigma\in\{(,)\}^*$:

$$\begin{array}{rlcl} i) & G_2\vdash(S\stackrel{*}{\rightarrow... ..., que incluso puede ser vac\'\i a. \end{minipage}} \end{array}$$

De hecho, estas relaciones pueden ser demostradas simultáneamente por inducción en el número de reglas aplicadas en G₂ para obtener la palabra $\sigma$. En efecto, supongamos que la relación ii) es verdadera. Entonces la i) también lo es, tan solo por la aplicación de la regla s). Ahora, si $\sigma$ se obtiene de A mediante una sola regla, esta regla ha de ser la a.1) y en este caso ii) se cumple. Si $\sigma$ se obtiene de n+1 reglas entonces la primera regla ha de ser cualquiera de a.2),a.3),a.4) las cuales son congruentes con la hipótesis ii). Ahora, para ver que G₂ subsume a G₁ hay que ver que toda cadena generada en G₁ es generada también en G₂. Para esto se procede también por inducción en el número de reglas aplicadas para generar una palabra terminal $\sigma$. Si $\sigma$ se obtiene mediante una sola regla en G₁, entonces esa regla ha de ser la 1. y $\sigma=()$. Una derivación de ella en G₂ es

$$S\stackrel{s}{\rightarrow}(A \stackrel{a.1}{\rightarrow}()$$

Ahora, supongamos que $\sigma$ se obtiene mediante la aplicación de n+1 reglas en G₁. Supongamos que la primera es de la forma 2.: $S\rightarrow (S)$. Entonces $\exists\sigma_1\in \mbox{\rm CEP}$ tal que $\sigma=(\sigma_1)$ y $\sigma_1$ se deriva con a lo sumo n aplicaciones de reglas en G₁. Por inducción, tenemos que $\sigma_1$ se deriva en G₂ y por la relación ii) tendremos $G_2\vdash[A\stackrel{*}{\rightarrow} \sigma_1)]$, de hecho, $G_2\vdash[A\stackrel{*}{\rightarrow} \sigma_1A]$. Así pues, una derivación de $\sigma$ en G₂ es

$$S\stackrel{s}{\rightarrow}(A \stackrel{*}{\rightarrow}(\sigma_1A \stackrel{a.1}{\rightarrow}(\sigma_1)=\sigma$$

Si la primera regla aplicada es 3.: $S\rightarrow SS$, entonces se construye de manera análoga una derivación en G₂. Así pues, las dos gramáticas dadas son equivalentes.
Siguiente: Tipos de gramáticas Un nivel arriba: Equivalencia de gramáticas Anterior: Equivalencia de gramáticas