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

Series en diccionarios

Sea G=(V,T,P,s0) una gramática libre de contexto. Para cada símbolo variable $v\in V$ sea $s_G=\{\sigma\in T^*\vert G\vdash s\stackrel{*}{\rightarrow}\sigma\}$ el conjunto de palabras derivadas por s en G. Así pues, el lenguaje de G es, (s0)G. De hecho, para cada palabra $\sigma\in (V\cup T)^*$ definamos

\begin{displaymath}\sigma_G=\{\sigma_1\in T^*\vert G\vdash \sigma\stackrel{*}{\rightarrow}\sigma_1\}.\end{displaymath}

Consideremos la transformación $(V\cup T)^*\rightarrow {\cal P}((V\cup T)^*)$, $\sigma \mapsto\sigma_G$, del diccionario $(V\cup T)^*$ a la clase de lenguajes ${\cal P}((V\cup T)^*)$. La operación ``suma'' de ${\cal P}((V\cup T)^*)$ es la unión conjuntista y su producto es el obtenido ``al concatenar lenguajes''

\begin{displaymath}L_1\cdot L_2=\{\tau_1\tau_2\vert\tau_1\in L_1,\tau_2\in L_2.\end{displaymath}

$\left({\cal P}((V\cup T)^*),+,\cdot\right)$ tiene una estructura de semianillo no-conmutativo, es decir, Ahora, para $(V\cup T)^*$ la ``alternancia'' puede ser vista como una suma, y por tanto $(\sigma_1+\sigma_2)_G=(\sigma_1)_G+(\sigma_2)_G$, y, ya que la gramática G es libre de contexto, se tiene también la identidad $(\sigma_1\sigma_2)_G=(\sigma_1)_G(\sigma_2)_G$. Así pues la transformación $\sigma \mapsto\sigma_G$ es un homomorfismo de semianillos. Consecuentemente, toda gramática libre de contexto puede ser presentada de manera algebraica: A cada producción de la forma $s\rightarrow \sigma_1\vert\cdots\vert\sigma_k$ se la escribe equivalentemente como $(s)_G=\sum_{\kappa=1}^k(\sigma_{\kappa})_G$, o bien, dando la gramática como supuesta, simplemente como la ecuación básica $s=\sum_{\kappa=1}^k\sigma_{\kappa}$. Ejemplos. 1. La gramática de cadenas equilibradas de paréntesis, $S\rightarrow ()\vert(S)\vert SS$ da la ecuación básica: S=()+(S)+SS.

2. La gramática de palíndromas $S\rightarrow \mbox{\it nil\/}\vert aSa\vert bSb$ da la ecuación básica: S=1+ aSa+bSb.

3. La gramática con producciones

\begin{displaymath}\begin{array}{rcl}
S &\rightarrow& a \\
S &\rightarrow& aA...
...bA \\
A &\rightarrow& SS \\
A &\rightarrow& ba
\end{array}\end{displaymath}

da las ecuaciones básicas

\begin{eqnarray*}S &=& a(1+AS) \\
A &=& ba + S(bA+S)
\end{eqnarray*}





Mediante sustituciones sucesivas se puede generar nuevas ecuaciones a partir de ecuaciones generadas previamente: La serie generativa del lenguaje L(G) se obtiene al tomar al ``supremo'' de todas las ecuaciones generadas a partir de la ecuación básica que tiene como extremo izquierdo al símbolo inicial. Como mero ejemplo, es fácil ver que para la ecuación básica S=1+ aSa+bSb la serie generativa quedará de la forma

\begin{displaymath}S=1+\sum_{n=1}^{+\infty} \sum_{\sigma\in(a+b)^n}\sigma\cdot\mbox{\it reverso\/}(\sigma).\end{displaymath}


next up previous contents
Siguiente: Series sobre los racionales Un nivel arriba: Series de potencias e Anterior: Series de potencias e
Guillermo Morales-Luna
2000-06-27