Discussion :

[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)

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...

[TheGwy]

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...

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 ?

[TheGwy]

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...

[TheGwy]

([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 !"

[Halex78]

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
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...

[Halex78]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(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.

[Obsidian]

Hello,

([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 Shell :

Sélectionner tout - Visualiser dans une fenêtre à part

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 Shell :

Sélectionner tout - Visualiser dans une fenêtre à part

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 Shell :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[TheGwy]

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ù ?

[Franck Dernoncourt]

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

[TheGwy]

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.

[Franck Dernoncourt]

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)

[TheGwy]

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.

[Franck Dernoncourt]

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