Theorie des langages - Trouver la grammaire d'un langage

[invite2c7e2526]

Bonsoir a tous
Bon voila je suis en train de reviser un module appellé théorie des langages. Je suis tombée sur un exercice que je trouve assez difficile à resoudre, je vous demande donc de bien vouloir m'aider et merci d'avance
L'exercice demande de trouver la grammaire, sachant que le langage L={a^m b^n c^l, l=max(n,m)}; n, m et l des entiers naturels..
J'ai deduit qu'il faut étudier les trois cas,
Cas 1:
quand n=m d'où l=n=m Ici je dois trouver la grammaire de L1={a^n b^n c^n avec n>=0} Je n'ai pas pu avancer ici et j'aimerais que vous m'aidiez s'il vous plait, je bloque

Cas 2:
Lorsque n<m d'où l=m On serait donc face à ce langage L2={a^m b^n c^m avec m>n, m>0, n>=0}

Cas 3:
Lorsque m<n alors l=n Le langage dans ce cas L3={a^m b^n c^n avec n>m, n>0, m>=0}

Je sais qu'à la fin je dois unir les 3 grammaires afin de repondre à l'exercice. Mais là j'arrive meme pas à trouver les 3 grammaires..
Merci beaucoup de votre aide.
-----

[Resartus]

Bonjour,
Je ne pense pas qu'il soit nécessaire de séparer en trois cas
Je suppose que vous avez étudié dans votre cours un exemple de grammaire pour a^n.b^n.c^n?
Si vous avez le droit de créer des mots vides, vous pouvez par exemple repartir de cette grammaire, et la modifier en rajoutant des règles qui permettent de supprimer à la fin un certain nombre,soit de a, soit de b, mais pas les deux à la fois.

[invite2c7e2526]

Bonjour,
Non on n'a pas abordé cet exemple en td ni en cours, du coup j'ai essayé de trouver la regle de production toute seule, le probleme c'est que je tombe toujours des regles de production fausses..

Pour le premier cas par exemple:
a^n b^n c^n avec n>=0
Une des regles de production que j'ai écrit:
S → aAbBcC/ε
A → a/ε
B →b/ε
C →c/ε
Ici la regle est fausse, car si on veut generer le mot ' aaabbbccc ' par exemple, A B et C doivent d'arreter ensemble au meme temps (avoir un epsilon dans A B et C simultanement), alors qu'ici ont peut avoir la possiblite de generer encore des a ou des b ou des c au lieu de s'arreter à epsilon comme est le cas pour le mot aaaabbbccc ...

Pourriez-vous, s'il vous plait m'aider à trouver le moyen qui me permettra d'avoir un epsilon juste apres avoir generer un nombre de a equivalent au nombre de b et de c ? J'ai essayé d'écrire d'autres regles de production un peu differentes mais je tombe souvent sur le meme probleme..

Quant à l'idée de supprimer un nombre de a ou de b ou c, on a jamais fait ça en cours et je n'ai aucune idée comment le faire. Je sais seulement comment generer des lettres mais de supprimer je ne vois pas du tout comment.. ?

[Resartus]

Bonjour,
Effectivement,si vous n'aviez jamais vu a^nb^c^n, ce n'est pas très facile à retrouver : un exemple ici : (page 2)
https://www.enseignement.polytechniq.../a15/a15.4.pdf

A partir de là, pour les suppressions*, on peut par exemple rajouter les règles aB->aDb et aB->aEb
On aura maintenant après aB, trois possibilités : ab, aDb, aEb (D servira pour supprimer des a, E pour les b)
puis ceci : aD->D, D->0, pour supprimer des a, puis s'arrêter, et idem Eb->E, E->0 pour supprimer des b et s'arrêter

*sous réserve que ce type de grammaire (type 0) vous soit autorisé

[A voir en vidéo sur Futura]

[Resartus]

Rebonjour,
A la réflexion, il y a plus simple et plus logique que ma proposition de suppression :
on peut commencer par décider au départ si on va créer plus de a que de b
et engendrer soit des D^nc^n soit des E^nc^n.
Ensuite, on transforme les D^n soit en Ab, soit en A (nombre de A toujours égal à n et b inférieur ou égal) et les E^n soit en aB soit en B (nombre de B toujours égal à n et a inférieur ou égal).
Puis on reclasse avec des règles Ba->aB, bA->Ab, et on finit par les conversions en a et b

[invite2c7e2526]

Bonsoir, désolée de ma réponse tardive, je suis très occupée en ce moment et la charge des études ne fait qu'empirer..
Je n'ai pas très bien compris votre deuxième méthode, j'ai donc appliqué la première, et j'ai ajouté vos règles de production à celle que j'ai trouvé dans le document, ce qui donne en tout:
S → 0
S → A
A → aABC/aBC
CB → BC
aB → ab/aDb/aEb
bC → bc
bB → bb
cC → cc
aD→D
D→0
Eb→E
E→0

Avec vos règles de production j'ai remarqué qu'on peut supprimer les a ou b pour obtenir par exemple ces mots: abbcc ou aabcc.. Je suis aussi tombée sur des cas bloqués comme aabcBC, est-ce normal ?
Une autre remarque, on ne peut pas générer les mots ac ou bc avec ces règles, j'ai donc ajouté quelques autres règles, ci-dessous, à mon point de vue elles sont correct, mais je ne suis pas 100% sûre, j'aimerais bien que vous m'aidiez en cas d'erreur ... Merci encore une fois de votre aide ! ^^
Pour former le mot ac :
aB→T
T →a
aTB→aab
aC→ac

Pour former le mot bc:
aB→K
aKB→aab
KC→bc