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,s₀) 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, (s₀)_G. De hecho, para cada palabra $\sigma\in (V\cup T)^*$ definamos

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

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''

$$L_1\cdot L_2=\{\tau_1\tau_2\vert\tau_1\in L_1,\tau_2\in L_2.$$

$\left({\cal P}((V\cup T)^*),+,\cdot\right)$ tiene una estructura de semianillo no-conmutativo, es decir,

• $\left({\cal P}((V\cup T)^*),+\right)$ es un monoide conmutativo con unidad el conjunto vacío, $0=\emptyset$,
• $\left({\cal P}((V\cup T)^*),\cdot\right)$ es un monoide con unidad la palabra vacía, $1=\mbox{\it nil\/}$, y
• $\cdot$ se distribuye por ambos lados respecto a +:
  
  $$\begin{eqnarray*}L_1(L_2+L_3) &=& L_1L_2+L_1L_3 \\ (L_2+L_3)L_1 &=& L_2L_1+L_3L_1 \end{eqnarray*}$$
  
  

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{array}{rcl} S &\rightarrow& a \\ S &\rightarrow& aA... ...bA \\ A &\rightarrow& SS \\ A &\rightarrow& ba \end{array}$$

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:

• toda ecuación básica es generada,
• si $s=F(\ldots, s_1,\ldots)$ es básica y s₁=G(V,T) ha sido generada entonces al sustituir s₁ por G(V,T) en $s=F(\ldots, s_1,\ldots)$,
  
  $$s=\left.F(\ldots, s_1,\ldots)\right\vert _{s_1=G(V,T)}$$
  
  
  da una nueva ecuación generada.

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

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

Siguiente: Series sobre los racionales Un nivel arriba: Series de potencias e Anterior: Series de potencias e