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{array}{ccl} \left.\begin{array}{rrcl} 1. & S &\right... ... \end{array} & : & \mbox{\it omite las $c$-es.\/} \end{array}$$

Efectivamente, esta nueva gramática genera a L₂: En cada generación, genera una palabra de L₃ y luego suprime el último bloque de c's. Evidentemente, L₂ 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.