Encontrar el lenguaje generado por una gramática libre de contexto

Esta es una pregunta del libro Dragon (pido disculpas por los errores de traducción, no tengo la versión en inglés a la mano):

¿Qué idioma genera esta gramática?

$S \rightarrow a S b S \mid b S a S \mid \epsilon$

No sé qué se supone que debo hacer aquí. La definición en el libro sobre idiomas dice esto (y eso es más o menos en el capítulo):

un lenguaje es el conjunto de todas las palabras que puede generar cualquier árbol de análisis.

Entonces, si quiero hacer "cualquier" árbol de análisis de esta gramática, puedo seguir construyéndolo recursivamente, usando solo las dos primeras reglas. Busqué un poco y tuve la impresión de que todas las reglas deben usarse una vez, pero no estoy seguro. Sería muy útil si alguien pudiera proporcionar algunos consejos para resolver este tipo de problemas.

formal-languages context-free formal-grammars dan
fuente

Sugerencia: utilice expresiones regulares

Bartosz Przybylski

Para consejos, vea las respuestas a continuación. En respuesta a su pregunta: no, no es necesario utilizar todas las reglas al menos una vez. Comience con el símbolo de inicio (o axioma) y aplique las reglas de reescritura hasta que le queden solo símbolos de terminal (en minúsculas).

Hendrik Jan

suponiendo que la cadena vacía no es un símbolo terminal, a mi entender, no es posible que solo queden símbolos terminales, ¿o no entiendo algo?

dan

Crossposted en cs.SE .

Raphael

@dan. La cadena vacía desaparece, por lo que puede terminar solo con terminales: . Por ejemplo.

S \Rightarrow a S b S \Rightarrow a a S b b S \Rightarrow a a b b S \Rightarrow a a b b b S a \Rightarrow a a b b b a

$S \Rightarrow aSbS \Rightarrow aaSbbS \Rightarrow aabbS \Rightarrow aabbbSa \Rightarrow aabbba$

Hendrik Jan

Respuestas:

Sugerencia: ¿Qué puede decir sobre el número de sy s en las palabras producidas? $a$ $b$

Sería muy útil si alguien pudiera proporcionar algunos consejos para resolver este tipo de problemas.

No hay una receta única para todos aquí. Es indecidible en general, si dos CFG producen el mismo idioma o si dos CFL son el mismo idioma. Un método útil es tratar de notar las propiedades que permanecen invariables durante las producciones.

Yo.
fuente

Sugerencia: construya algunas palabras generadas por esta gramática. ¿Ves un patrón? ¿Puedes describir algunas propiedades de todas las palabras generadas por la gramática, simplemente mirando las reglas? Una vez que tenga una suposición (correcta) sobre el lenguaje generado por la gramática, no será demasiado difícil demostrarlo.

Yuval Filmus
fuente