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

Elevación al cuadrado

Construiremos una gramática G que genere a las cadenas de 1's cuya longitud es el cuadrado de algún número natural positivo. Es decir, G ha de ser tal que L(G)=L donde $L=\{1^{n^2}\vert n\geq 1\}.$ Ya que para todo n, (n+1)2=n2+2n+1=n2+n+(n+1) y, al inicio, 12=1, la gramática, una vez que genera una cadena de longitud n2 ha de concatenarla con una de longitud n y otra de longitud n+1. Con esta motivación en mente, sea G la gramática cuyas producciones se presentan en la tabla (2.5) y cuyo símbolo inicial es S.
  
Table 2.5: Gramática para elevar al cuadrado en expresión unaria.
\begin{table}\begin{center}\fbox{\begin{minipage}[t]{25em}
\begin{eqnarray*}
\...
...semireiteraci\'on}
\end{eqnarray*}
\end{minipage}}\end{center}
\end{table}




Observaciones:
1.
En la tabla (2.6) se muestra la derivación de la cadena de longitud 25.
2.
Z es un delimitador derecho de cualquier cadena generada.
3.
Un ciclo de generación se obtiene entre dos derivaciones con la cadena WZ como sufijo.
4.
La generación de las cadenas de longitudes n2, $2\leq n \leq 7$, se muestra en la tabla (2.7).
5.
Ahí las cadenas generadas son de la forma 1V(VC+)*WZ. Sea $\sigma_n$ la cadena intermedia de la forma V(VC+)*. Para n>2 escribamos $\sigma_n=\tau_nVC^{2(n-2)}$. Entonces

\begin{displaymath}\begin{array}{lcl@{\;;\;}lcl}
\tau_2 &=& \mbox{\it nil\/}& \...
...}VC^{n-2} & \sigma_{n+1} &=& \tau_{n+1}VC^{2(n-1)}
\end{array}\end{displaymath}

Se ve que $\forall n:\ \ \mbox{\rm long}(\sigma_n)=n^2-3$.
6.
$G\vdash \sigma_nWZ\stackrel{*}{\rightarrow} \sigma_{n+1}WZ$.
7.
Una producción inicial genera: $1\cdot \sigma_2WZ$.
8.
Consecutivamente, se forma cualquier cadena de la forma $1\cdot \sigma_nWZ$.
9.
Al final a WZ se le cambia por 11 y a todas las V's y C's se les cambia también por 1.

 
Table 2.6: Derivación completa de longitud 52.
S
1VWZ
1VACVZ
1TCCVZ
1VVCWCCVZ
1VVCVBCVZ
1VVCVCBVZ
1VVCVCCWZ
1VVCVCCACVZ
1VVCVCACCVZ
1VVCVACCCVZ
1VVCTCCCCVZ
1VVACVCCCCVZ
1VTCCVCCCCVZ
1TCVCCVCCCCVZ
1VVCWCVCCVCCCCVZ
1VVCVBVCCVCCCCVZ
1VVCVCWCCVCCCCVZ
1VVCVCVBCVCCCCVZ
1VVCVCVCBVCCCCVZ
1VVCVCVCCWCCCCVZ
1VVCVCVCCVBCCCVZ
1VVCVCVCCVCBCCVZ
1VVCVCVCCVCCBCVZ
1VVCVCVCCVCCCBVZ
1VVCVCVCCVCCCCWZ
1VVCVCVCCVCCCCACVZ
1VVCVCVCCVCCCACCVZ
1VVCVCVCCVCCACCCVZ
1VVCVCVCCVCACCCCVZ
1VVCVCVCCVACCCCCVZ
1VVCVCVCCTCCCCCCVZ
1VVCVCVCACVCCCCCCVZ
1VVCVCVACCVCCCCCCVZ
1VVCVCTCCCVCCCCCCVZ
1VVCVACVCCCVCCCCCCVZ
1VVCTCCVCCCVCCCCCCVZ
1VVACVCCVCCCVCCCCCCVZ
1VTCCVCCVCCCVCCCCCCVZ
1TCVCCVCCVCCCVCCCCCCVZ
1VVCWCVCCVCCVCCCVCCCCCCVZ
1VVCVBVCCVCCVCCCVCCCCCCVZ
1VVCVCWCCVCCVCCCVCCCCCCVZ
1VVCVCVBCVCCVCCCVCCCCCCVZ
1VVCVCVCBVCCVCCCVCCCCCCVZ
1VVCVCVCCWCCVCCCVCCCCCCVZ
1VVCVCVCCVBCVCCCVCCCCCCVZ
1VVCVCVCCVCBVCCCVCCCCCCVZ
1VVCVCVCCVCCWCCCVCCCCCCVZ
1VVCVCVCCVCCVBCCVCCCCCCVZ
1VVCVCVCCVCCVCBCVCCCCCCVZ
1VVCVCVCCVCCVCCBVCCCCCCVZ
1VVCVCVCCVCCVCCCWCCCCCCVZ
1VVCVCVCCVCCVCCCVBCCCCCVZ
1VVCVCVCCVCCVCCCVCBCCCCVZ
1VVCVCVCCVCCVCCCVCCBCCCVZ
1VVCVCVCCVCCVCCCVCCCBCCVZ
1VVCVCVCCVCCVCCCVCCCCBCVZ
1VVCVCVCCVCCVCCCVCCCCCBVZ
1VVCVCVCCVCCVCCCVCCCCCCWZ


  
Table: Derivación de longitudes n2, $2\leq n \leq 7$.
\begin{table}\begin{displaymath}\begin{array}{l} \hline
\begin{array}{\vert l\v...
...&11V &+&35C \\ \hline
\end{array}
\end{array}\end{displaymath}
\end{table}


next up previous contents
Siguiente: Equivalencia de gramáticas Un nivel arriba: Ejemplos de gramáticas Anterior: Palabras dobles
Guillermo Morales-Luna
2000-06-27