Localizando o idioma gerado por uma gramática livre de contexto

Esta é uma pergunta do livro do Dragão (peço desculpas por erros de tradução, não tenho a versão em inglês):

Que idioma é gerado por esta gramática?

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

Não sei o que devo fazer aqui. A definição no livro sobre idiomas diz isso (e é isso mesmo no capítulo):

um idioma é o conjunto de todas as palavras que podem ser produzidas por qualquer árvore de análise.

Portanto, se eu quiser fazer "qualquer" árvore de análise dessa gramática, posso recursivamente continuar construindo-a, usando apenas as duas primeiras regras. Pesquisei um pouco e tive a impressão de que todas as regras devem ser usadas uma vez, mas não tenho certeza. Seria muito útil se alguém fosse capaz de fornecer algumas dicas para resolver esse tipo de problema.

formal-languages context-free formal-grammars dan
fonte

Dica: Use expressão regular

Bartosz Przybylski 18/13

Para dicas, veja as respostas abaixo. Em resposta à sua pergunta: não, não é necessário usar todas as regras pelo menos uma vez. Comece com o símbolo de início (ou axioma) e aplique as regras de reescrita até ficar apenas com símbolos de terminal (aqui em minúscula).

Hendrik Jan

supondo que a String vazia não seja um símbolo terminal, pelo que entendi, não é possível que apenas restem símbolos terminais, ou estou entendendo algo errado?

dan

Crossposted em cs.SE .

Raphael

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$

Respostas:

$a$ $b$

Seria muito útil se alguém fosse capaz de fornecer algumas dicas para resolver esse tipo de problema.

Não há receita única para todos aqui. É indecidível, em geral, se dois CFGs produzem o mesmo idioma ou dois CFLs são o mesmo idioma. Um método útil é tentar perceber as propriedades que permanecem invariáveis durante as produções.

Eu.
fonte

Dica: construa algumas palavras que são geradas por esta gramática. Você vê um padrão? Você pode descrever algumas propriedades de todas as palavras geradas pela gramática, apenas observando as regras? Depois de adivinhar (corretamente) o idioma gerado pela gramática, não será difícil provar isso.

Yuval Filmus
fonte