TD Automates, langages et applications Exercices Corrig´es TD 2 1

Automates, Langages et Applications - TD 2

1 Automates deterministes

Exercice 1 Dans chacun des cas suivants, donner un automate d´eterministe reconnaissant le langage sur l’alphabet { 0 , 1 } :

– l’ensemble des mots se terminant par 00 ;

– l’ensemble des mots ayant au moins 3 zeros cons´ecutifs ;

– l’ensemble des mots dont l’avant-dernier symbole est un 1 ;

– l’ensemble des mots qui contiennent au plus deux 0 cons´ecutifs et au plus deux 1 cons´ecutifs ;

– l’ensemble des mots commen¸cant par 1 qui, interpr´et´es comme des entiers en repr´esentation binaire, sont congrus `a 0 modulo 5.

Corrig´e :

0 , 1

0 , 1

0 1 2

1

1

0

3

1.

2.

1

0 0

1

0 0

0 0 1 2

1

1

0

1 00

0

0 01

0 ~~ ~~

10 1

• 1 0

[ ]

1

0

11

1 3.

1 0

1 1

1

0 1 0

[ ] [ ]

2

1

[ ]

0

0

1

0

0 1

1 [ ] [ ] [ ] [ ]

0 0

4 5

0

0

1

[ ] [ ] [ ]

0

1

1

0 3

0 4

4.

5. Chaque ´etat repr´esente la congruence modulo 5. Si x ≡ b [5], alors x 0 ≡ 2 b [5] et x 1 ≡ 2 b + 1 [5].

Universit´e Paris-Dauphine M1 Master MIAGE&D - 2009/2010 B, Escoffier, E. Lazard

2 Exercices Corrig´es TD 2 TD Automates, langages et applications

0

i

0

4

0

[ ]

1

~~ ~~ - 1

~~ ~~

~~ ~~

• 0 ~~ ~~

1

1

1

[ ]

1

∅

1

~~ ~~ - 1

~~ ~~

0 ~~ ~~

[ ] ~~[ ]~~ [ ][ ] - 0

~~ ~~ 0 1 ~~ ~~ - ~~ ~~ 0 [ ] 0

3 1

1

0

[ ]

0 , 1

0

0

2

Exercice 2 1. Soit l’alphabet Σ = {a, b}. Donner l’automate d´eterministe qui reconnaˆıt les mots qui contiennent ab. Peut-on construire facilement un automate reconnaissant les mots ne contenant pas ab? Pourriez-vous en d´eduire une m´ethode g´en´erale? 2. L’alphabet utilis´e devient Σ = {a, b, c}. Etendre [´] l’automate pr´ec´edent pour qu’il reconnaisse les mots contenant ab et commen¸cant par c. La m´ethode pr´ec´edente fonctionne-t-elle encore pour reconnaˆıtre les mots ne contenant pas ab ou ne commen¸cant pas par c?

Corrig´e :

1. L’automate suivant reconnaˆıt les mots contenant ab .

b

a 0

a

b 1

2

a,b

Pour reconnaˆıtre les mots ne contenant pas ab, il faut prendre son compl´ementaire, c’est -`a-dire transformer chaque ´etat final en non-final et vice-versa :

b

a 0

a

b 1

2

a,b

2. L’automate suivant reconnaˆıt les mots contenant ab et commen¸cant par c .

b,c

a

a,b,c

b 1

c -

− 1 0

a

b 1 2

c

Prendre le compl´ementaire ne suffit pas car les mots commen¸cant par a ou b ne sont pas reconnus (pas de transitions depuis l’´etat de d´epart). Le compl´ementaire doit ˆetre construit depuis un automate complet . Il faut donc rajouter un puits avec les transitions manquantes puis prendre le compl´ementaire :

b,c

a

a,b,c

b 1

c

− 1

c

0

a,b

[ ]

a

b 1 2

c

a,b

a,b,c

p

Universit´e Paris-Dauphine M1 Master MIAGE&D - 2009/2010 B, Escoffier, E. Lazard

TD Automates, langages et applications Exercices Corrig´es TD 2 3

Exercice 3 Donner l’automate d´eterministe reconnaissant les mots ayant un nombre pair de a et un nombre pair de b.

Corrig´e :

b pp

b

pi

a

a

a

a

ip

b ii

b

Exercice 4 Donner intuitivement le langage reconnu par l’automate suivant.

Corrig´e : Il s’agit du langage dont les mots ont un nombre impair de b .

Exercice 5 Montrer qu’un langage L fini est reconnaissable.

a b → 0 0 1 ∗ 1 1 0

Corrig´e : Il suffit de construire l’arbre n-aire de reconnaissance. Prenons un exemple. Si L = { 01 , 110 , 111 , 11 , 00 }, on construit l’automate :

1 0 [ ]

1

0

[ ]

1

1

0

0

1

[ ]

1

Exercice 6 Montrer que l’automate donn´e par la figure ci-dessous reconnaˆıt les mots compos´e d’au- tant de 0 que de 1 et dont chaque pr´efixe a au plus un 1 de plus que de 0 et au plus un 0 de plus que de 1.

0 0 1

1

0

1

0

1 - 3

2

0 , 1

Corrig´e : On dit qu’un mot est correct si chaque pr´efixe a au plus un 1 de plus que de 0 et au plus un 0 de plus que de 1. On proc`ede par r´ecurrence et on va montrer que :

• δ ( q 0 , x ) = q 0 ⇔ x est correct et a autant de 0 que de 1 ;

• δ ( q 0 , x ) = q 1 ⇔ x est correct et a un 0 de plus que de 1 ;

Universit´e Paris-Dauphine M1 Master MIAGE&D - 2009/2010 B, Escoffier, E. Lazard

4 Exercices Corrig´es TD 2 TD Automates, langages et applications

• δ ( q 0 , x ) = q 2 ⇔ x est correct et a un 1 de plus que de 0 ;

• δ ( q 0 , x ) = q 3 ⇔ x n’est pas correct.

Si |x ] = 0, alors x = ε et δ ( q 0 , ε ) = q 0 et ε a autant de 0 que de 1.

⇒ Soit |y| = n avec y correct et ayant autant de 0 que de 1.

1. Si y = x 0, x est correct et δ ( q 0 , x ) = q 2 et donc δ ( q 0 , y ) = δ ( q 2 , 0) = q 0.

2. Si y = x 1, x est correct et δ ( q 0 , x ) = q 1 et donc δ ( q 0 , y ) = δ ( q 1 , 1) = q 0.

Soit |y| = n avec y correct et ayant un 1 de plus que de 0. Si y = x 0, alors x a deux 0 de moins que de 1 et n’est pas correct. C’est impossible car x est un pr´efixe de y qui ne serait alors pas correct non plus. Donc y = x 1 et donc x a autant de 0 que de 1, donc δ ( q 0 , x ) = q 0 et donc δ ( q 0 , y ) = δ ( q 0 , 1) = q 2.

Idem si y a un 0 de plus que de 1 ou n’est pas correct.

⇐ Supposons que δ ( q 0 , y ) = q 0 avec |y| ≥ 1. Si y = x 0, alors δ ( q 0 , x ) = q 2 (car il faut apres arriver en _q_ 0 en lisant un 0) donc par hypothese de r´ecurrence, x est correct et a un 1 de plus que de 0. Donc y est correct avec autant de 0 que de 1.

Idem si y = x 1 et si δ ( q 0 , y ) = q 1 , q 2 ou q 3.

Exercice 7 On consid`ere le dispositif ci-dessous

Une bille est lach´ee en A ou B (A = 0 , B = 1 ). Les trois leviers font tomber la bille a_ _gauche_ _ou_ _a droite. De plus, lorsqu’une bille passe sur un levier, celui-ci change d’orientation apres._ _Mod´eliser_ _le_ _dispositif_ _avec_ _un_ _automate,_ _une_ _s´equence_ _´etant_ _accept´ee_ _si_ _la_ _derniere bille sort en D.

Corrig´e : Un ´etat est caract´eris´e par la position des trois leviers et de la sortie de la derniere bille. L’´etat _qi_ corresponda la valeur i en binaire sur l 3 l 2 l 1 o`u / = 0 et __ = 1.

Universit´e Paris-Dauphine M1 Master MIAGE&D - 2009/2010 B, Escoffier, E. Lazard

TD Automates, langages et applications Exercices Corrig´es TD 2 5

0

0 −D 1 −D

 1 _−_ _D_ ** ** 0 _−_ _C_ 

0 −D

1 −D

0 −C

3

 1 _−_ _D_ ** ** 0 _−_ _C_ 

2

0 −D

1 −D

1 −C

1 −C

0 −C

[ ][ ]

1 −C 0 −C

[ ] 0 − C [ ] 1 − D [ ]

[ ]

0 − C [ ] 1 − D

[ ]

0 −C

[ ]

1 −D

 - 
 - 
 - 
 - 
- 
- 
-

• • • -
    • 1 − - D 0 − C 3 0 − C 1 − C 1 − 0 −D

• • • [ ][ ] 6

0 −C

1 −D

0 −C

0 −C

5

0 −D

1 −D

1 −D

0 −C

0 −C

[ ]

1 −D

[ ]

0 −C

1 −C

[ ]

[ ]

0 −C

1 −C

[ ]

[ ]

1 −D

0 −C

[ ][ ]

0 −C

[ ]

1

0 −D

0 −C

1 −D

0 −D

1 −D

0 −D

1 −C

1 −D

7

0 −C

0 −C

1 −D

4

En fait, chaque ´etat est divis´e en 2, suivant que la derni`ere bille est sorti en C ou en D. Seuls les ´etats D sont finaux bien sˆur. Les transitions partant des deux ´etats sont les mˆemes mais arrivent soit sur un ´etat C, soit sur un ´etat D, comme indiqu´e sur la transition.

Universit´e Paris-Dauphine M1 Master MIAGE&D - 2009/2010 B, Escoffier, E. Lazard