Exámenes

Buenas tardes Wilson,

la tira que ponés de ejemplo ( $aaaabbbc\#b\#b$ ) pertenece al lenguaje y está bien que se derive de la gramática. Vayamos paso a paso.

El lenguaje es $L_2 = \{x=a^j b^k c^l(\#b)^{j-k+l}: j>k \geq 0 \wedge l>0\}$ . Reordenando un poco las potencias, nos queda
$L_2 = \{x=a^jb^kc^l(\#b)^l(\#b)^{j-k}: j>k\geq0 \wedge l>0\}$

Pero además, como $j>k$ podemos decir que $j=k+s$ con $s>0$. Entonces reescribimos:
$L_2 = \{x=a^{k+s}b^kc^l(\#b)^l(\#b)^s: k\geq0 \wedge l>0 \wedge s>0 \}$ y reordenamos de nuevo los índices:

$L_2 = \{x=a^s a^k b^k c^l (\#b)^l (\#b)^s: k\geq0 \wedge l>0 \wedge s>0 \}$ 

Una vez obtenida esa expresión, veamos cómo se relaciona con cada regla de producción:

• S -> aS#b: esta regla es por si se quiere tener un valor de $s\geq2$. En caso de que $s=1$ no se usa.
  
• S -> XC#b: esta regla es para terminar de formar las dependencias del índice $s$ y pasar a formar las de $k$ (con la variable $X$) y las de $l$ (con la variable $C$). El $\#b$ del final es para asegurar que  $s>0$, y su $a$ compañera va a estar en la última derivación de $X$.
  
• X -> aXb: aquí se generarían los $k$ pares de a y b
  
• X -> a: y este es el mencionado símbolo que acompaña al $\#b$ de la regla S -> XC\#b, para obligar a $s>0$.
  
• C -> cC#b: esta regla permite generar pares de $c$ y $\#b$ para cuando $l>1$
  
• C -> c#b: y esta regla permite asegurar $l>0$