[théorie, automates, regexp] matcher sigma(a,b,c) sans matcher "baa"

Bonjour, je suis en train de potasser "Modern Compilers Implementation in Java" et je bloque sur un exercice, voici l'énoncé (traduit par mes soins)

Ecrire une expression régulière qui couvre tout l'alphabet {a,b,c} mais qui ne match pas la substring "baa".

La ou ça se corse c'est que l'on est pas dans une belle plateforme plein de fioriture mais vraiment sur la théorie des automates donc on a pas tout plein de fonctions vachement pratiques comme les lookahead, ancres, classes négatives... On as le droit qu'au 3 opérateurs fondamentaux des regexp :

- la concaténation
- l'union
- l'étoile de Kleene

J'arrive assez facilement à écrire l'Automate Déterministe Fini qui réponds à l'énoncé, mais la regexp j'avoue que je coince...

PS : c'est pour ma culture perso, non je ne suis plus étudiant depuis belle lurette... :mouarf:

Bon en fait non, je viens de trouver une transition dans mon automate qui valide (ba?b)*aa ...

Donc du coup je ne suis pas avancé d'un iota... :calim2:

EDIT : en plus je me rends compte que je suis sur le forum regex de PHP... Le message aurait peut etre plus sa place en algorithmie ou à la limite en Perl ^^;
Un modo peut il déplacer SVP ?

Bon je pense avoir trouvé, comme quoi on a toujours l'illumination quand on commence à demander aux autres !

Je vous épargne l'automate déterministe qui est très rébarbatif. Le version non-déterministe par contre est plus courte :

3 états S0, S1 et S2 tous finaux
et 5 transitions étendues :
extended-delta(S0, ac) = S0;
extended-delta(S0, b) = S1;
extended-delta(S1, a[epsilon]) = S2;
extended-delta(S2, b) = S1;
extended-delta(S2, c) = S0;

Par contre je bloque toujours sur la transformation de l'automate en regexp...

([ac]((ba?)*c)?)*(ba?)*c*

Je crois bien que la j'ai bon !



---------
Ce topic vous est offert par le syndicat des monologuistes : "Les monologues ça marche !"

Bonjour, je ne sais pas si tu as trouvé la solution à ton problème, mais je te dis comment moi j'aurais fait.

1. Tu commences par créer un automate déterministe complet qui reconnait le langage des mots qui contiennent au moins une occcurence de bba.
2. Cet automate reconnaissant ce langage, ce que tu veux, c'est tout sauf ça, tu veux donc le complémentaire de ce langage, donc à partir de cet automate complet (sans blocage donc...), tu crées l'automate qui reconnait le complémentaire de ce langage, en inversant états finals, et états non finals.
3. à partir de ce nouvel automate, tu en déduis l'expression régulière grâce à l'algorithme d'élimination des états, McNaughton et Yamada, ou encore avec le Lemme d'Arden, perso je préfère l'algorithme d'élimination des états, mais chacun ses caprices :mrgreen:
4. Normalement, même si l'expression régulière est assez gore, elle est juste, et tu peux éventuellement essayer de la simplifier.

Voilà, j'espère avoir été utile, sinon ca servira peut être à quelqu'un d'autre...

Voilà l'expression régulière que je trouve avec ma méthode :

Code:

---

(a|c|bb*c|(b(a|c))*)*

---

J'ai peut être mal compris le problème par contre. si j'ai bon, ne t'étonnes pas de trouver un résultat différent du mien, on peut en avoir un différent, selon la manière de procéder... Cela n'empêche pas que plusieurs résultats différents peuvent être bons.

Salut,

l'expression que j'ai posté m'a l'air de marcher. Bon par contre je n'ai pas vraiment de méthode formelle pour retranscrire l'automate en regex.
Et je commence tout juste à aborder les réductions d'automates. En tout cas ta méthode (décrire l'automate inverse puis trouver le complémentaire) me semble intéressante.

La regex par contre match "baa" (en passant une première fois par la dernière alternative pour avoir "ba" puis une deuxième fois pour obtenir le dernier "a".

Ah pardon, je l'ai fait avec "bba", la méthode marche aussi avec "baa" bien sûr.
Pour retranscrire en regex un automate, ben il faut utiliser une des 3 méthodes que j'ai proposées, je ne sais pas s'il en existe d'autres.

Citation:

---

Envoyé par TheGwy

Bonjour, je suis en train de potasser "Modern Compilers Implementation in Java" et je bloque sur un exercice, voici l'énoncé (traduit par mes soins)

---

N'hésite pas à laisser des messages en anglais ;)

Oui je suis en train de suivre le cours sur les automates justement.
J'ai un peu de mal à suivre le rythme car je n'ai pas de vrai formation en algèbre derrière (autodidacte inside) mais pour l'instant je me débrouille.

:ccool:

Par curiosité quelles sont les notions en algèbre que tu penses manquer lorsque tu suis le cours sur les automates ? (je le fais également)

Par exemple je ne comprends pas les moments où M. Ullman parle de preuves formelles et démontre certains théorèmes.

PS : je ne me suis pas encore penché sur les cours de la troisième semaine.

ok, merci !
Je t'avoue que je n'ai pas eu le temps de vraiment me pencher sur le cours, j'ai surtout fait les exercices pour me faire une piqûre de rappel sur les automates.
Bonne continuation pour le reste du cours :)

Hello,

Citation:

---

Envoyé par TheGwy

([ac]((ba?)*c)?)*(ba?)*c*
Je crois bien que la j'ai bon !

---

Avec cette formule, je ne retrouve effectivement aucun « baa » dans les résultats. Par contre, j'ai beaucoup de faux positifs. Exemple :

Code:

---

1 2 3 4 5 6 7 8 9 10

$ echo "bbabcbbaabcbcbcbaabbccaacccbbbcaaacabbbbaaaccbcccacbbccaccbbaacaccbabcaaaacaccacbaaccaaccbaacabbbaacabcbcaccaabcbccbacbcbaabacacababcaacbcccbaccacaabcbaaccbcabccbccbcbbcbabccaa" | egrep -o '([ac]((ba?)*c)?)*(ba?)*c*' bbabc bba abcbc bc ba abbccaacccbbbcaaacabbbba aaccbcccacbbccaccbba acaccbabcaaaacaccacba …

---

En revanche, avec le Lemme d'Arden, j'obtiens ceci : « a*(ca*|b|ba)* ».

Code:

---

1 2 3 4 5 6 7 8 9 10 11

$ echo "bbabcbbaabcbcbcbaabbccaacccbbbcaaacabbbbaaaccbcccacbbccaccbbaacaccbabcaaaacaccacbaaccaaccbaacabbbaacabcbcaccaabcbccbacbcbaabacacababcaacbcccbaccacaabcbaaccbcabccbccbcbbcbabccaa" | egrep -o 'a*(ca*|b|ba)*' bbabcbba abcbcbcba abbccaacccbbbcaaacabbbba aaccbcccacbbccaccbba acaccbabcaaaacaccacba accaaccba acabbba acabcbcaccaabcbccbacbcba abacacababcaacbcccbaccacaabcba accbcabccbccbcbbcbabccaa

---

… à chaque fois, la césure tombe bien sur la troisième lettre de « baa », et on n'en trouve aucun dans les motifs renvoyés :

Code:

---

1 2	$ echo "bbabcbbaabcbcbcbaabbccaacccbbbcaaacabbbbaaaccbcccacbbccaccbbaacaccbabcaaaacaccacbaaccaaccbaacabbbaacabcbcaccaabcbccbacbcbaabacacababcaacbcccbaccacaabcbaaccbcabccbccbcbbcbabccaa" | egrep -o 'a*(ca*|b|ba)*' | grep 'baa' $

---

On voit également que toutes les lignes se terminent par « ba… » et reprennent par « …a ». En outre, on ne perd aucune lettre de cette façon.

Ah oui effectivement !!

Par contre je ne comprends pas pourquoi la mienne ne fonctionne pas... Lorsque je "l'execute" mentalement j'arrive pourtant bien à faire correspondre l'entrée au pattern.

Si je reprends ton exemple : "bbabcb" ne fais pas partit du langage ([ac]((ba?)*c)?)*(ba?)*c*

Pourtant :
bbabcb ([ac]((ba?)*c)?)*(ba?)*c*
bbabcb ([ac]((ba?)*c)?)*(ba?)*c*
bbabcb ([ac]((ba?)*c)?)*(ba?)*c*
bbabcb ([ac]((ba?)*c)?)*(ba?)*c*
bbabcb ([ac]((ba?)*c)?)*(ba?)*c*

De toute évidence je fais erreur, mais où ?

Laisse tomber je viens de comprendre !
Je ne rentre jamais dans mon premier groupe de capture car la string ne commence pas par [ac]...


Edit : par contre mon NDA est bien correct, c'est vraiment ma transformation qui est fausse. Je vais me pencher sur les méthodes formelles de conversion, car mon intuition, sur ce coup, est loin d'être fiable. :aie:

Citation:

---

Envoyé par TheGwy

Edit : par contre mon NDA est bien correct, c'est vraiment ma transformation qui est fausse. Je vais me pencher sur les méthodes formelles de conversion, car mon intuition, sur ce coup, est loin d'être fiable. :aie:

---

Pourquoi as-tu écrit un NDA ? Pour reconnaître « baa », je n'ai besoin que de quatre états et mon automate est déterministe. Par contre, je fais l'hypothèse que l'alphabet se résume à {a,b,c}.