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,s₀), 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 X_s. 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 p_L de L(G) corresponde con una serie $\Phi(p_l)$ en $I\!\!\!\!Q[[\mbox{\bf X}]]$. Observamos dos características:

• la serie generativa no involucra a los símbolos de V, pues esta serie se expande hasta la supresión de los símbolos variables, y
• todas las palabras que son permutaciones de un mismo ``multiconjunto'' se símbolos corresponden a un mismo monomio en $I\!\!\!\!Q[[\mbox{\bf X}]]$:
  
  $$\begin{eqnarray*}ababab,abbbaa,bababa,\ldots &\mbox{\rm corresponden a}& X_a^3X_... ...,abbbaba,babbaba,\ldots &\mbox{\rm corresponden a}& X_a^3X_b^4 \end{eqnarray*}$$
  
  

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(Y²+Z²)+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

$$X=ZY+ZXY+XX=X^2+X\cdot ZY +ZY$$

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 b₀=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 b₀=0. Con esta elección de b₀ se tiene determinados a los demás coeficientes b_m. 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{array}{rrcll} 1. & S &\rightarrow& SbS &\mbox{\it\beg... ...} term\'\i nese con una \lq\lq a''. \end{minipage}\/} \end{array}$$

El lenguaje generado por la gramática es

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

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=YX²+1. Al resolverla con la fórmula de Lagrange 6.3 se tiene

$$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.$$

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

$$X=1+\sum_{m\geq 1} \frac{1}{m+1}{2m\choose m}Y^m$$

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.
Siguiente: Programas Un nivel arriba: Series de potencias e Anterior: Series sobre los racionales