Langages réguliers et hors-contexte
Cours
M1 INaLCO, 2008-2009
Interrogation
écrite du 18/12/08 : Commentaires sur les commentaires...
- Les
commentaires en fin de ligne : "
//[^\n]*\n"
- Commentaires à la C et en fin de ligne : réunion des deux e.r.
- Contre-épreuve
L'énoncé
Les expressions régulières qu'on utilise en pratique
mettent en jeu la plupart du temps des classes de caractères,
désignées soit par des paires de crochets (par exemple [0-9]),
soit par des abrévations conventionnelles (par exemple \d).
Mais, pour dessiner des automates sans se tromper, il faut revenir à
des transitions provoquées par des lettres individuelles.
C'est en effet la seule manière de s'assurer que l'automate est
déterministe en vérifiant que chaque état reçoit son lot complet de
transitions, sans manque et sans doublon. Il faut donc avant toute
chose représenter par une seule lettre chaque classe de caractères en
jeu, et s'assurer que ces classes sont disjointes.
Les deux automates à construire ici vont illustrer ce procédé.
1.
Les commentaires en fin de ligne : "//[^\n]*\n"
Nous désignerons par n le
saut de ligne et par a la
classe [^\n] des
caractères autres que n et
que /.
L'alphabet de notre automate est donc à trois lettres {/,
n, a}.
Comme le montre l'inspection des 3 transitions de chaque sommet, cet
automate est déterministe.
Ce que le logiciel automate confirme à sa manière,
en le dessinant comme suit (avec renumérotation des états) :
Il est en outre manifestement minimal, aucun état ne jouant le même
rôle qu'un autre.
À nouveau, automate confirme en le
dessinant tel quel, sauf l'état-poubelle.
2.
Commentaires à la C et en fin de ligne : réunion des deux e.r.
Cette fois nous avons besoin des 3 caractères individuels /,
*, n, et d'une
classe a qui désigne tous
les autres
(et pas seulement "ni /,
ni *" comme dans la donnée
de l'automate des commentaires à la C,
et pas non plus "autre que n"
comme ci-dessus).
L'alphabet de notre automate à construire est donc à quatre lettres {/, *,
n, a}.
Puisqu'on demande un automate déterministe, la construction va suivre
le principe donné au cours n° 5,
en prenant pour états les couples d'états des deux automates, et en se
bornant à ceux qui peuvent être atteints
au cours d'un calcul commençant en l'état initial (0,0).
Les deux automates en question sont
- en première composante celui que nous avons dessiné plus
haut
pour les commentaires en fin de ligne, avec ses 4 états dont la
poubelle n° 4.
- en seconde composante l'automate de l'énoncé pour les
commentaires à la C,
avec 5 états dont la poubelle n° 5.
Par la lettre / ,
l'état initial (0,0)
est envoyé sur le couple (1,1).
Par les 3 autres lettres, il est envoyé sur le couple (4,5),
qui aura clairement un comportement de poubelle
dans notre nouvel automate.
Par la lettre / ,
l'état (1,1) est
envoyé sur le couple (2,5),
par la lettre *
sur le couple (4,2)et par n,
a sur la poubelle (4,5).
Vu la nature des deux états-poubelle 4
et 5, à partir de (2,5)
le calcul va se poursuivre comme dans le premier automate
(puisque la seconde composante restera fixée à 5),
et à partir de (4,2) comme
dans le second (puisque la première composante restera fixée à 4).
Du côté du premier, nous aurons donc une boucle sur (2,5) avec
les lettres /, *,
a, et une transition vers (3,5) par
n.
L'état (3,5) est
terminal, et toutes les lettres l'envoient sur la poubelle (4,5).
Du côté du second, nous aurons une boucle sur (4,2)avec
les lettres /, n,
a, et une transition vers (4,3) par *.
(4,3) par *,
une transition de retour de (4,3)
vers (4,2) par n,
a, et une transition vers (4,4) par /.
(4,4) est
terminal, et toutes les lettres l'envoient sur la poubelle (4,5).
On obtient ainsi l'automate déterministe à 8 états dont une poubelle et
2 terminaux que voici :
Cet automate n'est pas minimal car les deux états terminaux jouent
manifestement le même rôle, on peut donc les confondre.
Mais on ne peut pas aller plus loin dans la réduction.
En numérotant (0,0) -> 0, (1,1)
-> 1, (2,5)
-> 2, (3,5)
-> 3, (4,2)
-> 4, (4,3)
-> 5, (4,4)
-> 6,
et (4,5) ->
7, on obtient dans automate
le portrait flatteur que voici :
Comme précédemment, le logiciel confirme que cet automate est déterministe en le redessinant de manière
plus concise :
et il le réduit sous la forme :
3.
Contre-épreuve :
À partir de cet automate minimal, le logiciel engendre l'expression régulière suivante :
//(a|/|*)*n|/*(n|a|/)**(*|(n|a)(n|a|/)**)*/
Évidemment cette expression (en syntaxe standard) est ambiguë car le
générateur n'a pas su distinguer la lettre '*'
de l'opérateur homonyme.
Mais nous pouvons lever l'ambiguïté à la main, en plaçant les
occurrences de la lettre entre crochets. Il vient :
//(a|/|[*])*n|/[*](n|a|/)*[*]([*]|(n|a)(n|a|/)*[*])*/
où nous retrouvons bien nos deux composantes "//(a|/|[*])*n"
et "/[*](n|a|/)*[*]([*]|(n|a)(n|a|/)*[*])*/".
Pour donner cette expression à automate, il faut
demander la syntaxe étendue à la LEX,
ce qui entraîne par défaut la construction directe d'un automate déterministe.
Cet automate s'avère être minimal :
