next up previous contents
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),

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

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


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 P1 consta de las reglas

\begin{displaymath}S\rightarrow ()\vert(S)\vert SS.\end{displaymath}

De acuerdo con las reglas descritas arriba, G1 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.)
\begin{table}\begin{displaymath}\begin{array}{cc}
\begin{array}{\vert\vert l\ve...
...{array} \vspace{3ex}
\\ (a) & (b)
\end{array}\end{displaymath}
\end{table}

Consideremos ahora la gramática G2 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 G1 subsume a G2, es decir, que toda palabra terminal generada en G2 es generada también en G1, basta observar que para cualquier $\sigma\in\{(,)\}^*$:

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

De hecho, estas relaciones pueden ser demostradas simultáneamente por inducción en el número de reglas aplicadas en G2 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 G2 subsume a G1 hay que ver que toda cadena generada en G1 es generada también en G2. 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 G1, entonces esa regla ha de ser la 1. y $\sigma=()$. Una derivación de ella en G2 es

\begin{displaymath}S\stackrel{s}{\rightarrow}(A \stackrel{a.1}{\rightarrow}()\end{displaymath}

Ahora, supongamos que $\sigma$ se obtiene mediante la aplicación de n+1 reglas en G1. 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 G1. Por inducción, tenemos que $\sigma_1$ se deriva en G2 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 G2 es

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

Si la primera regla aplicada es 3.: $S\rightarrow SS$, entonces se construye de manera análoga una derivación en G2. Así pues, las dos gramáticas dadas son equivalentes.
next up previous contents
Siguiente: Tipos de gramáticas Un nivel arriba: Equivalencia de gramáticas Anterior: Equivalencia de gramáticas
Guillermo Morales-Luna
2000-06-27