Trouver le langage généré par une grammaire sans contexte

Ceci est une question du livre Dragon (je m'excuse pour les erreurs de traduction, je n'ai pas la version anglaise sous la main):

Quelle langue est générée par cette grammaire?

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

Je ne sais pas ce que je suis censé faire ici. La définition dans le livre sur les langues dit ceci (et c'est à peu près tout dans le chapitre):

une langue est l'ensemble de tous les mots qui peuvent être produits par n'importe quel arbre d'analyse.

Donc, si je veux créer "n'importe quel" arbre d'analyse à partir de cette grammaire, je peux continuer à le construire récursivement, en utilisant seulement les deux premières règles. J'ai cherché un peu et j'ai eu l'impression que chaque règle doit être utilisée une fois, mais je ne suis pas sûr. Il serait très utile que quelqu'un puisse fournir des conseils sur la résolution de ce type de problèmes.

formal-languages context-free formal-grammars dan
la source

Astuce: Utilisez une expression régulière

Bartosz Przybylski

Pour des conseils, voir les réponses ci-dessous. En réponse à votre question: non, il n'est pas nécessaire d'utiliser chaque règle au moins une fois. Commencez avec le symbole de début (ou axiome) et appliquez les règles de réécriture jusqu'à ce que vous ne soyez plus qu'avec des symboles terminaux (ici en minuscules).

Hendrik Jan

en supposant que la chaîne vide n'est pas un symbole terminal, à ma connaissance, il n'est pas possible qu'il ne reste que des symboles terminaux, ou ai-je mal compris quelque chose?

dan

Crossposted sur cs.SE .

Raphael

@dan. La chaîne vide disparaît, vous pouvez donc vous retrouver avec des terminaux uniquement: . Par exemple.

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

Réponses:

Astuce: Que pouvez - vous dire sur le nombre d' s et s dans les mots produits? $a$ $b$

Il serait très utile que quelqu'un puisse fournir des conseils sur la résolution de ce type de problèmes.

Il n'y a pas de recette unique ici. Il est indécidable en général, que deux CFG produisent la même langue ou que deux CFL soient la même langue. Une méthode utile consiste à remarquer les propriétés qui restent invariantes pendant les productions.

Moi.
la source

Astuce: Construisez quelques mots qui sont générés par cette grammaire. Peut-tu discerner une structure logique? Pouvez-vous décrire certaines propriétés de tous les mots générés par la grammaire, simplement en regardant les règles? Une fois que vous avez une supposition (correcte) sur le langage généré par la grammaire, il ne sera pas trop difficile de le prouver.

Yuval Filmus
la source