Ejemplos

¿Es posible derivar lenguajes infinitos con sistemas de producciones finitos?

Si, por ejemplo es posible generar el lenguaje $L(G)=\Sigma_T^*$ con un sistema de producciones finitos:

$$G=(\{\$\},\{a,b\},\{\$\longrightarrow \epsilon,\$\longrightarrow a\$,\$\longrightarrow b\$\},\$)$$

$$\begin{eqnarray*} L_1 &=& \{\epsilon,a,b\} \\ G_1 &=& (\{\$\},\{a,b\},\{\$\longrightarrow \epsilon,\$\longrightarrow a,\$\longrightarrow b\},\$) \end{eqnarray*}$$

• obviamente $L(G_1)=L_1$
• para lenguajes finitos es fácil generar una gramática, basta con derivar directamente cada palabra desde el símbolo inicial (aunque se puede usar un sistema de producciones más sofisticado)

Una gramática recursiva sobre la palabra $v\in\mbox{$\Sigma^*$}$ es una gramática donde se puede derivar desde $v$ una palabra que contiene $v$ de nuevo, es decir, existe la posibilidad de una derivación: $v\longrightarrow ^*uvw$ (con $\vert v\vert<\vert uvw\vert$).

El lenguaje generado por una gramática es infinito, si la gramática es recursiva sobre una palabra $v$ y que a su vez es derivable desde el símbolo inicial.

$$\begin{eqnarray*} L_{ab} &=& \{a^nb^n\;\vert\;n\in\bbbn\} \\ G_{ab} &=& (\{a,b\},\{\$\},\{\$\longrightarrow a\$b,\$\longrightarrow \epsilon\},\$) \end{eqnarray*}$$

$$\begin{eqnarray*} L_{abc} &=& \{a^nb^nc^n\;\vert\;n\in\bbbn\} \\ & & \epsilon,... ...c,\dots\in L_{abc} \\ G_{abc} &=& (\{\$,\dots\},\{a,b,c\},P,\$) \end{eqnarray*}$$

• ¿Cuáles son las producciones necesarias?
• Una vez sabiendo eso, podemos completar el alfabeto no-terminal $\Sigma_N$
• Una primera idea:
  $$\begin{eqnarray*} P&=&\{\$\longrightarrow \epsilon,\$\longrightarrow ABC,A\long... ...rrow \epsilon,C\longrightarrow cC\} \\ \Sigma_N&=&\{\$,A,B,C\} \end{eqnarray*}$$
  
  
  Obviamente podemos derivar cualquier elemento de $L_{abc}$ con esa gramática, por ejemplo:
  $$\begin{eqnarray*} \$&\longrightarrow &ABC\longrightarrow aABC\longrightarrow aa... ...ngrightarrow aabbcC\longrightarrow aabbccC\longrightarrow aabbcc \end{eqnarray*}$$
  
  
  Pero también podemos derivar palabras como $aaabcccc$, es decir, el lenguaje es
  
  $$L(G_{\mathrm{Test}})=\{a^ib^jc^k\;\vert\;i,j,k\in\bbbn\}\supset L_{abc}$$
  
  
  Parece que la gramática $G_{\mathrm{Test}}$ es demasiado amplia. De alguna manera deberíamos construir un sistema de producciones que permite mantener un número igual de letras $a$, $b$ y $c$ (o en otras palabras, necesitamos ``contar'')...

• Idea 1: Si somos capaz de derivar desde $a^kXb^kc^k$ la secuencia $a^{k+1}Xb^{k+1}c^{k+1}$, hemos ganado.

  Idea 2: Tenemos que pasar la ``información'' que hemos añadido por ejemplo un $ab$ en un lado hacia el otro lado donde tenemos que añadir entonces una $c$ (o en un lado la $a$ y en el otro lado un $bc$).

  El truco consiste en usar unos símbolos no-terminales cuales se van a sustituir dependiendo del contexto en el cual se encuentran.

  Entonces, construimos $P$ y $\Sigma_N$:

  $$\begin{eqnarray*} P &=&\{\\ && \begin{array}{lcll} \$ &\longrightarrow & \epsil... ...a terminar} \end{array} &&\} \\ &&\\ \Sigma_N&=&\{\$,X,Y,Z\} \end{eqnarray*}$$
  
  

• Se puede comprobar formalmente con inducción sobre $k$ que la gramática dada genera exactamente el lenguaje deseado, es decir $L(G_{abc})=L_{abc}$.

  La comprobación sigue la construcción y se observa que no hay ambigüedad en el momento de elegir una producción.

• Existe también una gramática que usa un símbolo no-terminal menos y también una producción menos:
  $$\begin{eqnarray*} P &=&\{\\ && \begin{array}{lcll} \$ &\longrightarrow & \epsil... ...ara terminar} \end{array} &&\} \\ &&\\ \Sigma_N&=&\{\$,X,Y\} \end{eqnarray*}$$
  
  
  Se observa:
  • tenemos ambigüedad en elegir producciones para sustituir y dónde aplicarlas
  • aquí hemos decidido añadir a la derecha una $b$ y una $c$
  • generalmente se nota que hay muchas gramáticas que generan el mismo lenguaje