problema de gramática libre de contexto

Question

$L$ es la gramática libre de contexto sobre $\{a, b\}$

$S \rightarrow aSb \; | \;bR \; |\;Ra$

$R \rightarrow bR \;|\;aR\;|\;\epsilon$

Describa brevemente esta CFG con frases en inglés y demuestre su descripción. A continuación, dé una CFG para el complemento de $L$ .

$\\$

Creo que el CFG es un lenguaje con igual cantidad de $a$ al principio y $b$ al final, en el medio con una cadena que consiste en $a$ y $b$ y que empiece por $b$ o termina con $a$ . Pero no estoy seguro de que sea correcto ni sé cómo probar formalmente mi descripción.

Para el complemento, no estoy seguro de cómo diseñar el CFG.

¿Alguien puede resolver este problema? Gracias.

Answer 1

Ha observado que el lenguaje generado por $\newcommand{\a}{\mathtt{a}}\newcommand{\b}{\mathtt{b}}L$ parece ser exactamente la colección de todas las cadenas de las dos formas siguientes

1. $w = \a^\ell \b v \b^\ell$ o
2. $w = \a^\ell v \a \b^\ell$

para alguna cadena $v \in \{ \a , \b \}^*$ .

Para demostrar que la CFG genera exactamente estas cadenas nos limitaremos a demostrar que cada una de ellas puede ser generada por $L$ y cada cadena generada por $L$ es de una de esas dos formas. (Esto será bastante manual, pero las ideas pueden hacerse formales).

Si $w = \a^\ell \b v \b^\ell$ y después de aplicar la regla $S \rightarrow \a S \b$ $\ell$ veces hemos $\a^\ell S \b^\ell$ . A partir de aquí aplicar la regla $S \rightarrow \b R$ para conseguir $\a^\ell \b R \b^\ell$ y es sencillo demostrar que el "sub-CFG" formado sólo por el $R$ -reglas puede generar cada cadena sobre $\{ \a , \b \}$ . Si $w = \a^\ell v \a \b^\ell$ procedemos de manera similar, pero tomamos la regla $S \rightarrow R \a$ en el punto adecuado.

Para demostrar que toda cadena generada por $L$ es de una de las formas anteriores, tenga en cuenta que cualquier generación debe aplicar la regla $S \rightarrow \a S \b$ $\ell$ muchas veces (para algunos $\ell \geq 0$ ), dando como resultado $\a^\ell S \b^\ell$ y luego aplicar la regla $S \rightarrow \b R$ o $\mathtt{S} \rightarrow R \a$ , dando lugar a $\a^\ell \b R \b^\ell$ , $\a^\ell R \a \b^\ell$ respectivamente. A partir de aquí utilizamos el $R$ reglas para generar alguna subcadena $v$ lo que resulta en $\a^\ell \b v \b^\ell$ , $\a^\ell v \a \b^\ell$ .

Para diseñar un CFG para el complemento del lenguaje anterior, sólo dejaré una pista:

Una pista: Para cada cadena $w \in \{ \a , \b \}^*$ hay un número entero mayor $\ell \geq 0$ tal que $w = \a^\ell v \b^\ell$ para alguna cadena $v$ . Tenga en cuenta que $v$ no puede ser de la forma $\a u \b$ para alguna subcadena $u$ (ya que $\ell$ se tomó como el mayor posible). Pero entonces, ¿qué formas posibles pueden $v$ ¿toma? ¿Y cuál de estas posibilidades no puede ser generada por $L$ ¿ por encima?

Las respuestas correctas a las preguntas de la pista deberían dar lugar a una descripción más sencilla del lenguaje generado por $L$ (ya que en realidad existe una descripción bastante sencilla del complemento).

Answer 2

Dejemos que $A = \{a,b\}$ . Entonces la lengua $L$ es la menor solución en $S$ del sistema de ecuaciones \begin {align} S &= aSb + bR + Ra \\ R &= bR + aR + 1 \end {align} donde $+$ denota la unión y $1$ denota la palabra vacía. La segunda ecuación da $R = (a+b)R + 1 = AR + 1$ y tiene $R = A^*$ como solución única. Al informar en la primera ecuación se obtiene $S = aSb + bA^* + A^*a$ . Configuración $K = bA^* + A^*a$ se puede escribir como $S = aSb + K$ , lo que lleva a la solución $$ L = \{ a^nub^n \mid n \geqslant 0 \text{ and } u \in K \} $$ Para la segunda parte, no tengo nada que añadir a la excelente sugerencia de Arthur Fischer.