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)²=n²+2n+1=n²+n+(n+1) y, al inicio, 1²=1, la gramática, una vez que genera una cadena de longitud n² 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.

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 n², $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{array}{lcl@{\;;\;}lcl} \tau_2 &=& \mbox{\it nil\/}& \... ...}VC^{n-2} & \sigma_{n+1} &=& \tau_{n+1}VC^{2(n-1)} \end{array}$$

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 5².

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 n², $2\leq n \leq 7$.

Siguiente: Equivalencia de gramáticas Un nivel arriba: Ejemplos de gramáticas Anterior: Palabras dobles