next up previous contents
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.
\begin{table}\begin{displaymath}\begin{array}{rrcll}
1. & S &\rightarrow& ABC &...
...
term\'\i nese
\end{minipage}\/}
\end{array}\end{displaymath}
\end{table}

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.
\begin{table}\begin{displaymath}\begin{array}{\vert\vert l\vert\vert l\vert\vert...
...ray} & 10011001 \\
\hline \hline
\end{array}\end{displaymath}
\end{table}

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.

next up previous contents
Siguiente: Elevación al cuadrado Un nivel arriba: Ejemplos de gramáticas Anterior: Parejas de igual longitud
Guillermo Morales-Luna
2000-06-27