Siguiente: Elevación al cuadrado Un nivel arriba: Ejemplos de gramáticas Anterior: Parejas de igual longitud

Palabras dobles

Sea $L=(0+1)^{(2)}=\{\sigma\sigma\vert\sigma\in (0+1)^*\}$ el lenguaje que consta de las palabras formadas por la repetición de una partícula en el alfabeto $\{0,1\}$. Una gramática que genera al lenguaje L es la gramática G mostrada en la tabla (2.3).

  

Table 2.3: Gramática que genera repeticiones de palabras.

Una derivación de la palabra $1001\,1001\in L$ se muestra en la tabla (2.4).

  

Table 2.4: Un ejemplo en la generación de repeticiones.

Del ejemplo mostrado y de las producciones en la tabla (2.3) podemos ver que los símbolos tienen los efectos siguientes:

S	:	símbolo inicial,
A	:	delimitador derecho del primer bloque,
B	:	``cursor'' para seguir añadiendo símbolos en los bloques generados,
C	:	delimitador derecho del segundo bloque,
D	:	recordatorio de que se ha generado un 0,
E	:	recordatorio de que se ha generado un 1.

El procedimiento seguido por la gramática es el siguiente:

1.

Del símbolo inicial genera un área de trabajo, ABC: a la izquierda de A está la palabra vacía y a la izquierda de C también está la palabra vacía.

2.

Cada vez que A y B sean adyacentes,

(a)

genera, inmediatamente a la izquierda de A, un símbolo $x\in\{0,1\}$ y su correspondiente recordatorio X, X=D si x=0 y X=E si x=1,

(b)

traslada X hacia la izquierda de C,

(c)

en esa posición escribe x y recupera a B,

(d)

traslada B a ser adyacente a A,

3.

o bien suprime AB cuando ya no vaya a generar más símbolos.

4.

Suprime C.

Siguiente: Elevación al cuadrado Un nivel arriba: Ejemplos de gramáticas Anterior: Parejas de igual longitud