next up previous contents
Siguiente: Programas Un nivel arriba: Series de potencias e Anterior: Series sobre los racionales

Conteo de árboles de derivación

Para una gramática libre de contexto G=(V,T,P,s0), su serie generativa puede hacérse corresponder con una serie en $I\!\!\!\!Q[[V\cup T]]$ de manera que las ecuaciones impuestas por las producciones en P se satisfagan también en $I\!\!\!\!Q[[V\cup T]]$. En efecto, a cada símbolo s en $V\cup T$ asociémosle una incógnita Xs. Sea $\mbox{\bf X}=[X_s\vert s\in V\cup T]$. Tratemos ahora el producto de incógnitas como si fuera conmutativo, pues de hecho lo es en $I\!\!\!\!Q[[\mbox{\bf X}]]$. Con esto, la serie generativa pL de L(G) corresponde con una serie $\Phi(p_l)$ en $I\!\!\!\!Q[[\mbox{\bf X}]]$. Observamos dos características: Consecuentemente, el coeficiente de un monomio en la serie $\Phi(p_l)$ es el número de posibles árboles de derivación derivables en G correspondientes a una palabra sobre el multiconjunto correspondiente al monomio. Esta transformación da así un método para contar derivaciones. Si la gramática no es ambigua, entonces cada palabra del lenguaje corresponde a un único árbol y, consecuentemente, éste procedimiento cuenta palabras generadas. Ejemplos. 1. Para la gramática que genera palíndromas pares ( $S\rightarrow aSa\vert bSb\vert\mbox{\it nil\/}$) o sea S=aSa+bSb+1 consideremos la correspondencia inducida por

\begin{eqnarray*}S &\mapsto& X \\
a &\mapsto& Y \\
b &\mapsto& Z
\end{eqnarray*}


La producción da la ecuación

X=YXY+ZYZ+1=X(Y2+Z2)+1

y por tanto $X=\frac{1}{1-\left(Y^2+Z^2\right)}$. La serie $\Phi(p_L)$ correspondiente a la serie generativa ha de ser solución de esta última ecuación. Por tanto, según se vió en la proposición 6.5.2 de la anterior sección,

\begin{eqnarray*}X &=& \sum_{m\geq 0}\left(Y^2+Z^2\right)^m \\
&=& \sum_{m\geq 0}\sum_{k=0}^m{m\choose k} Y^{2(m-k)}Z^{2k}
\end{eqnarray*}


Así pues para cada $m\geq 0$ hay ${\displaystyle \sum_{k=0}^m{m\choose k}=2^m}$ posibles árboles para palabras de longitud 2m, y para cada $k\leq m$ hay ${m\choose k}$ árboles para palabras de longitud 2m con 2k apariciones del símbolo b. Como la gramática no es ambigua, la cuenta de árboles correponde a la cuenta de palabras.


2. Para la gramática de cadenas equilibradas de paréntesis [ $S\rightarrow ()\vert(S)\vert SS$] o sea S=()+(S)+SS consideremos la correspondencia inducida por

\begin{eqnarray*}S &\mapsto& X \\
) &\mapsto& Y \\
( &\mapsto& Z
\end{eqnarray*}


La producción da la ecuación

\begin{displaymath}X=ZY+ZXY+XX=X^2+X\cdot ZY +ZY\end{displaymath}

y por tanto $X^2+X\cdot (ZY-1) +ZY=0$. Consideremos por un momento Z=1. Entonces tenemos la ecuación 6.2 de la sección anterior. Consecuentemente, X tiene dos soluciones de la forma $X=\sum_{m\geq 0}b_mY^m$ donde b0=0,1 y

\begin{eqnarray*}b_1 &=& \frac{1+b_0}{1-2b_0} \\
\forall m\geq 2:\ \ b_m &=& \...
...}\left( b_{m-1}+\left(\sum_{k=1}^{m-1} b_kb_{m-k}\right)\right)
\end{eqnarray*}


En nuestro caso no hay ninguna paabra equilibrada con 0 paréntesis derechos. Así pues, el término independiente de la serie generativa debe ser b0=0. Con esta elección de b0 se tiene determinados a los demás coeficientes bm. Cada uno de ellos da el número de árboles de derivación de cadenas equilibradas de paréntesis para formar cadenas equilibradas con m paréntesis derechos. Como la gramática es ambigua el número de árboles excede el de cadenas equilibradas.


3. Consideremos la gramática con producciones

\begin{displaymath}\begin{array}{rrcll}
1. & S &\rightarrow& SbS &\mbox{\it\beg...
...}
term\'\i nese con una \lq\lq a''.
\end{minipage}\/}
\end{array}\end{displaymath}

El lenguaje generado por la gramática es

\begin{displaymath}L(G)=\{\left(ab\right)^na\vert n\geq 0\}.\end{displaymath}

La gramática se expresa por la ecuación S=SbS+a y mediante la correspondencia

\begin{eqnarray*}S &\mapsto& X \\
b &\mapsto& Y \\
a &\mapsto& 1
\end{eqnarray*}


se tiene la ecuación X=YX2+1. Al resolverla con la fórmula de Lagrange 6.3 se tiene

\begin{displaymath}X=1+\sum_{m\geq 1} \frac{1}{m!}\left[\left.\frac{\textstyle d^{m-1}}{\textstyle dx^{m-1}}x^{2m}\right\vert _{x=1}\right] Y^m.\end{displaymath}

Para cada $m\geq 1$ se tiene

\begin{eqnarray*}\frac{1}{m!}\left[\left.\frac{\textstyle d^{m-1}}{\textstyle dx...
...2m)!}{(m+1)!}x^{m+1} \\
&=& \frac{1}{m+1}{2m\choose m}x^{m+1}
\end{eqnarray*}


Al evaluar en el punto x=1 obtenemos

\begin{displaymath}X=1+\sum_{m\geq 1} \frac{1}{m+1}{2m\choose m}Y^m\end{displaymath}

lo cual significa que para cada m hay derivaciones de la única palabra (ab)ma generable en la gramática que contiene exactamente m b's.
next up previous contents
Siguiente: Programas Un nivel arriba: Series de potencias e Anterior: Series sobre los racionales
Guillermo Morales-Luna
2000-06-27