Trouver une grammaire hors-contexte pour le langage L

[invitea5398569]

Bonjour,
Je n'ai pas trouvé de rubrique correspondante à l'informatique théorique sur le forum info, alors je pose ma question ici.

J'ai une langue et je dois trouver une grammaire hors-contexte (ou algébrique) correspondant à ce langage. Le problème c'est que je ne sais pas trop comment faire.

J'ai remarqué que :
- Tous les mots ont une longueur paire
- Si m augmente de 1, nécessairement p ou q augmente de 1.
- Si n augmente de 1, nécessairement p ou q augmente de 1.

Mais je n'arrive pas à transformer ça en transitions dans ma grammaire (N ensemble des symboles non-terminaux, T = , P ensemble des transitions, S symbole de départ appartenant à N).
Comment pourrais-je raisonner ?
-----

[Resartus]

Bonjour,
Il y a surement d'autres possibilités, mais on peut (par exemple) partir avec une création du type S->bc et bc->bbcc, qui donnera un nombre égal de b et de c, puis convertir un certain nombre de b en tête en a et un certain nombre de c en queue en d....

[invitea5398569]

Bonjour,
Merci de votre réponse.

Malheureusement, une grammaire hors-contexte possède des propriétés particulières, principalement les transitions de P sont toujours de la forme , avec . Je ne peux donc pas appliquer votre méthode.

Le problème c'est la condition m+n=p+q. Mais comme je ne peux pas ajouter les d et les a n'importe comment, ça me bloque un peu.

Je suis en train de chercher une grammaire en associant avec des transitions du type A > aBb par exemple.

[invite23cdddab]

Quelque chose comme ça ne ne conviendrait pas?

A -> bAc | epsilon
B -> bBd | bAd
C -> aCc | aAc
D -> aDd | aAd | aBd | aCd

[A voir en vidéo sur Futura]

[invitea5398569]

Quelque chose comme ça ne ne conviendrait pas?

A -> bAc | epsilon
B -> bBd | bAd
C -> aCc | aAc
D -> aDd | aAd | aBd | aCd

C'est ce que je viens de trouver, en remplaçant D par S et en ajoutant epsilon aux transitions de S, B, C (des mots peuvent être formés sans utiliser b ou c ^^)