IUT Info 1A
Annee 2007-08
Periode 1
B. Gugger
F. Madelaine
C. Simon
D. Richard
Graphes et Automates
Feuille de TD n2
Les polycopies du cours, les feuilles de TD et quelques corriges sont disponibles `a
lurl suivante.
http ://laic.u-clermont1.fr/~fmadelaine/teaching/graphe1.html
D
eterminisation
Lid
ee
On va simuler en meme temps plusieurs etats dun automate non-deterministe. Concr`etement,
on consid`ere maintenant des super-etats qui sont des ensemble detats. On utilise alors la
methode suivante.
Un super-etat qui ne contient que des etats initiaux est initial ;
Un super-etat qui contient un etat final est final ; et,
Un super etat S transite en lisant une lettre a vers le super-etat S 0 , qui est lunion, pour
tout etat s de S, de lensemble de tous les etats s0 , tels que s transite vers s0 en lisant
la lettre a.
Mise en oeuvre
On determinise1 lautomate suivant.
senter la fonction de transition de lautomate
deterministe.
remarque
initial
final
super-etat
{0}
{1}
{1, 2}
a
{1}
{1}
{1}
{1, 2}
{1, 2}
Cest-`a-dire lautomate deterministe suivant.
Comme les supers-etats qui ne sont pas accessibles depuis les super-etats initiaux ne
servent `a rien, on ne calcule que ceux qui sont
accessibles. On utilise un tableau pour repreExercice 1. Construire un automate fini deterministe equivalent `a lautomate suivant.
D
eterminiser : (verbe) rendre deterministe. Ne pas confondre avec D
eterminer : (verbe) calculer.
feuille de TD n 2
Graphe et Automates
Combiner des automates
On dispose de lautomate A1 qui reconnat le langage L1 et de A2 qui reconnat L2 . On cherche
`a construire `
a partir de A1 et de A2 lautomate pour les langages L1 L2 , L1 + L2 et L1 L2 .
Concat
enation
Somme (union)
On construit lautomate pour le langage
On construit lautomate pour le langage
L = L1 L2
L = L1 + L2
L = {w1 w2 tel que w1 L1 et w2 L2 }.
L = {w tel que w L1 ou w L2 }.
On a ajoute des arcs entre les etats finaux de
M1 (qui ne sont plus finaux dans le nouvel automate) et les etats initiaux de M2 . Ces arcs
sont des transitions particuli`eres, qui ne lisent
aucune lettre, autrement dit le mot vide . On
parle alors de -transition.
Produit (intersection)
On construit lautomate pour le langage L = L1 L2 = {w tel que w L1 et w L2 }.
On a des etats doubles : letat (h, 6) correspond simultanement `a letat h de A1 et `a letat 6
de A2 . Le nouvel automate simule de mani`ere synchronisee les transitions de A1 et A2 .
2
feuille de TD n 2
Graphe et Automates
Exercice 2. Soit A1 lautomate dessine `a gauche et A2 celuis de droite. Soient L1 et L2 leurs
langage respectifs.
a - Construire lautomate de L1 L2 .
b - Meme question mais sans -transition.
c - Construire lautomate de L1 + L2
d - Construire lautomate de (L1 )? L2
e - Construire lautomate de L1 L2
Des automates aux langages
Le lemme dArden
Ce resultat dit que lequation recursive suivante
X = LX + M
o`
u X est le langage cherche et L et M sont deux langages connus, a une unique solution qui
est :
X = L? M.
Attention : ici, on suppose que L ne contient pas le mot vide.
M
ethode du syst`
eme des d
eparts
On cherche `
a determiner le langage de lauto- Par le lemme dArden sur la seconde equamate suivant.
tion, il vient L2 = b? (aL1 ).
En recrivant la premi`ere, on a
L1 = + aL1 + b(b? aL1 )
= + aL1 + b+ aL1
On sinteresse au langage L1 des mots qui
= b? aL1 +
passent par letat 1, et `
a L2 celui des mots
qui passent par 2.
On a les equations suivantes.
(
Par le lemme dArden sur cette equation, on
L1 = +aL1 + bL2
obtient finalement que :
L2 =
aL1 + bL2
L1 = (b? a)? = (b? a)? .
Ici apparat puisque letat 1 est initial.
feuille de TD n 2
Graphe et Automates
Exercice 3. Determiner le langage reconnu par lautomate suivant.
Exercice 4. On consid`ere le syst`eme dequations suivant :
L1 = aL1 + bL2 + cL3
L2 = cL2 + bL1 + aL3
L3 = c + aL2 + bL3
Trouver lexpression rationnelle de L1 .
Exercice 5. Determiner le langage reconnu par lautomate de lexercice 1.
Exercice 6. a - Donner lexpression rationnelle du langage reconnu par lautomate ci-dessous.
b - Determiniser cet automate.
Exercice 7. Soit le langage sur lalphabet = {a, b} constitue des mots dont la derni`ere
lettre apparat au moins une fois dans la partie initiale (i.e. dans le mot prive de sa derni`ere
lettre).
a - Trouver un automate A non deterministe reconnaissant L.
b - Trouver un automate A non deterministe `a 4 etats reconnaissant L.
c - Determiniser lautomate A.
d - Trouver une expression rationnelle designant L.
Exercice 8. On consid`ere lalphabet = {a, b, c}.
a - Construire un automate deterministe qui reconnat le langage a ba + a+ b c.
b - Meme question pour (a ba + a+ b c) .
c - Meme question pour ca + c b.
d - Meme question pour (a ba + a+ b c) (ca + c b)
Exercice 9. Donner un automate deterministe qui reconnat les mots sur {a, b} ne contenant
ni le facteur a2 ni le facteur b3 et qui sont de taille multiple de 3. En donner lexpression
rationnelle.
4
