Siguiente: Parejas de igual longitud Un nivel arriba: Ejemplos de gramáticas Anterior: Proposiciones bien formadas

Tercetas de igual longitud

Sea $L_3=\{a^kb^kc^k\vert k\geq 1\}$ el lenguaje que consta de tres bloques consecutivos de a's, b's y c's de iguales longitudes. Construiremos una gramática para generar este lenguaje. Consideremos las producciones siguientes:

$$\begin{array}{rrcll} 1. & S &\rightarrow& A &\mbox{\it\begin... ...variables por $c$-es terminales \end{minipage}\/} \end{array}$$

En la tabla (2.2) vemos, a manera de ejemplo, la generación de la palabra a³b³c³=aaabbbccc.

  

Table 2.2: Un ejemplo para la gramática de L₃.

Con la gramática descrita, tenemos, efectivamente, que

i)

toda palabra generada en ella tiene una longitud múltiplo de 3, y

ii)

toda palabra generada es de la forma a^kb^kc^k para algún $k\geq 0$.

Así pues, el lenguaje generado por la gramática es $L(\mbox{\rm gram\'atica})=L_3$.