TD Automates, langages et applications Exercices Corrigés TD 2 1

Automates, Langages et Applications - TD 2

1 Automates deterministes

Exercice 1 Dans chacun des cas suivants, donner un automate déterministe 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écutifs ;

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

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

– l’ensemble des mots commençant par 1 qui, interprétés comme des entiers en représentation binaire, sont congrus à 0 modulo 5.

Corrigé :

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 état représente la congruence modulo 5. Si x ≡ b [5], alors x 0 ≡ 2 b [5] et x 1 ≡ 2 b + 1 [5].

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

2 Exercices Corrigés 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éterministe 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éduire une méthode générale? 2. L’alphabet utilisé devient Σ = {a, b, c}. Etendre [´] l’automate précédent pour qu’il reconnaisse les mots contenant ab et commençant par c. La méthode précédente fonctionne-t-elle encore pour reconnaˆıtre les mots ne contenant pas ab ou ne commençant pas par c?

Corrigé :

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émentaire, c’est -à-dire transformer chaque état 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çant par c .

b,c

a

a,b,c

b 1

c -

− 1 0

a

b 1 2

c

Prendre le complémentaire ne suffit pas car les mots commençant par a ou b ne sont pas reconnus (pas de transitions depuis l’état de départ). Le complémentaire doit être construit depuis un automate complet . Il faut donc rajouter un puits avec les transitions manquantes puis prendre le complémentaire :

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é Paris-Dauphine M1 Master MIAGE&D - 2009/2010 B, Escoffier, E. Lazard

TD Automates, langages et applications Exercices Corrigés TD 2 3

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

Corrigé :

b pp

b

pi

a

a

a

a

ip

b ii

b

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

Corrigé : 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é : 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é par la figure ci-dessous reconnaˆıt les mots composé d’au- tant de 0 que de 1 et dont chaque préfixe 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é : On dit qu’un mot est correct si chaque préfixe a au plus un 1 de plus que de 0 et au plus un 0 de plus que de 1. On procède par récurrence 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é Paris-Dauphine M1 Master MIAGE&D - 2009/2010 B, Escoffier, E. Lazard

4 Exercices Corrigés 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éfixe 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écurrence, 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ère le dispositif ci-dessous

Une bille est lachée 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éliser_ _le_ _dispositif_ _avec_ _un_ _automate,_ _une_ _séquence_ _étant_ _acceptée_ _si_ _la_ _derniere bille sort en D.

Corrigé : Un état est caractérisé par la position des trois leviers et de la sortie de la derniere bille. L’état _qi_ corresponda la valeur i en binaire sur l 3 l 2 l 1 où / = 0 et __ = 1.

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

TD Automates, langages et applications Exercices Corrigés 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 état est divisé en 2, suivant que la dernière bille est sorti en C ou en D. Seuls les états D sont finaux bien sûr. Les transitions partant des deux états sont les mêmes mais arrivent soit sur un état C, soit sur un état D, comme indiqué sur la transition.

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