next up previous contents
Siguiente: Palabras dobles Un nivel arriba: Ejemplos de gramáticas Anterior: Tercetas de igual longitud

Parejas de igual longitud

Sea $L_2=\{a^kb^k\vert k\geq 1\}$. Construiremos una gramática para este lenguaje siguiendo el esquema de la gramática anterior. Consideremos las siguientes producciones:

\begin{displaymath}\begin{array}{ccl}
\left.\begin{array}{rrcl}
1. & S &\right...
...
\end{array} & : & \mbox{\it omite las $c$-es.\/}
\end{array}\end{displaymath}

Efectivamente, esta nueva gramática genera a L2: En cada generación, genera una palabra de L3 y luego suprime el último bloque de c's. Evidentemente, L2 se genera también por la gramática $S\rightarrow aSb\vert ab$. Así pues, un mismo lenguaje puede ser generado por más de una gramática.

Guillermo Morales-Luna
2000-06-27