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é :
1.
2.
3.
1
0
1
0
0
1
0
2
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
1
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
1
0
1
0
1
0
2
0
3
0,1
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
1
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
1
00
0
(cid:95)(cid:94)(cid:93)(cid:92)
(cid:88)(cid:89)(cid:90)(cid:91)
0
01
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:95)(cid:94)(cid:93)(cid:92)
0
10
1
(cid:32)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)(cid:65)
1
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:95)(cid:94)(cid:93)(cid:92)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:88)(cid:89)(cid:90)(cid:91)
0
11
1
(cid:95)(cid:94)(cid:93)(cid:92)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:88)(cid:89)(cid:90)(cid:91)
0
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
1
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
1
0
1
(cid:31)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)
0
1
0
(cid:95)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)
(cid:127)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)
1
2
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:31)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)
1
3
0
4
0
5
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
0, 1
4.
5. Chaque état représente la congruence modulo 5.
Si x ≡ b [5], alors x0 ≡ 2b [5] et x1 ≡ 2b + 1 [5].
Université Paris-Dauphine
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:47)
(cid:47)
(cid:108)
(cid:108)
(cid:9)
(cid:9)
(cid:105)
(cid:105)
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:47)
(cid:47)
(cid:108)
(cid:108)
(cid:47)
(cid:47)
(cid:105)
(cid:105)
(cid:9)
(cid:9)
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:85)
(cid:85)
(cid:47)
(cid:47)
(cid:32)
(cid:108)
(cid:108)
(cid:117)
(cid:117)
(cid:79)
Publicité
(cid:79)
(cid:85)
(cid:85)
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:31)
(cid:47)
(cid:47)
(cid:12)
(cid:12)
(cid:127)
(cid:31)
(cid:47)
(cid:47)
(cid:76)
(cid:76)
(cid:47)
(cid:47)
(cid:95)
(cid:85)
(cid:85)
2
Exercices Corrigés TD 2
TD Automates, langages et applications
0
i
0
(cid:2)(cid:4)(cid:4)(cid:4)(cid:4)(cid:4)(cid:4)(cid:4)(cid:4)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
1 (cid:15)
∅
1
0
1
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:121)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)(cid:114)
(cid:72)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)(cid:18)
(cid:53)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)(cid:108)
(cid:28)(cid:58)(cid:58)(cid:58)(cid:58)(cid:58)(cid:58)(cid:58)(cid:58)
(cid:2)(cid:4)(cid:4)(cid:4)(cid:4)(cid:4)(cid:4)(cid:4)(cid:4)
0
1
0
1
0
0
1
4
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
0, 1
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
2
1
3
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
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 conte-
nant pas ab? Pourriez-vous en déduire une méthode générale?
2. L’alphabet utilisé devient Σ = {a, b, c}. Étendre 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
a,b
2
Pour reconnaˆıtre les mots ne contenant pas ab, il faut prendre son complémentaire, c’est
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
-à-dire transformer chaque état final en non-final et vice-versa :
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
b
a
0
a
b
1
a,b
2
2. L’automate suivant reconnaˆıt les mots contenant ab et commençant par c.
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
−1
c
0
b,c
a
c
a
b
1
2
a,b,c
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:95)(cid:94)(cid:93)(cid:92)
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 :
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:95)(cid:94)(cid:93)(cid:92)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
−1
c
0
(cid:31)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)(cid:64)
a,b
a
b
1
2
a,b,c
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
b,c
a
c
a,b,c
p
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
Université Paris-Dauphine
Publicité
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard
(cid:43)
(cid:51)
(cid:15)
(cid:2)
(cid:121)
(cid:9)
(cid:9)
(cid:52)
(cid:52)
(cid:28)
(cid:38)
(cid:38)
(cid:2)
(cid:9)
(cid:9)
(cid:72)
(cid:53)
(cid:111)
(cid:111)
(cid:102)
(cid:102)
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:9)
(cid:9)
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:9)
(cid:9)
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:44)
(cid:44)
(cid:9)
(cid:9)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:108)
(cid:108)
(cid:9)
(cid:9)
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:31)
(cid:44)
(cid:44)
(cid:9)
(cid:9)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:108)
(cid:108)
(cid:9)
(cid:9)
(cid:9)
(cid:9)
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é :
pp
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:95)(cid:94)(cid:93)(cid:92)
a
a
ip
b
b
b
b
pi
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:95)(cid:94)(cid:93)(cid:92)
a
a
ii
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:95)(cid:94)(cid:93)(cid:92)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
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.
a
0
1
b
1
0
→ 0
∗ 1
Exercice 5 Montrer qu’un langage L fini est reconnaissable.
Corrigé :
{01, 110, 111, 11, 00}, on construit l’automate :
Il suffit de construire l’arbre n-aire de reconnaissance. Prenons un exemple. Si L =
(cid:39)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)
0
1(cid:15)
(cid:47)(cid:46)(cid:45)(cid:44)
(cid:40)(cid:41)(cid:42)(cid:43)
1(cid:15)
(cid:47)(cid:46)(cid:45)(cid:44)
(cid:40)(cid:41)(cid:42)(cid:43)
1(cid:15)
(cid:47)(cid:46)(cid:45)(cid:44)
(cid:24)(cid:25)(cid:26)(cid:27)
(cid:31)(cid:30)(cid:29)(cid:28)
(cid:40)(cid:41)(cid:42)(cid:43)
(cid:31)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)
0
(cid:31)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)
1
0(cid:15)
(cid:47)(cid:46)(cid:45)(cid:44)
(cid:40)(cid:41)(cid:42)(cid:43)
(cid:24)(cid:25)(cid:26)(cid:27)
(cid:47)(cid:46)(cid:45)(cid:44)
(cid:31)(cid:30)(cid:29)(cid:28)
(cid:40)(cid:41)(cid:42)(cid:43)
(cid:24)(cid:25)(cid:26)(cid:27)
(cid:47)(cid:46)(cid:45)(cid:44)
(cid:31)(cid:30)(cid:29)(cid:28)
(cid:40)(cid:41)(cid:42)(cid:43)
(cid:24)(cid:25)(cid:26)(cid:27)
(cid:31)(cid:30)(cid:29)(cid:28)
(cid:40)(cid:41)(cid:42)(cid:43)
(cid:47)(cid:46)(cid:45)(cid:44)
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.
(cid:24)(cid:25)(cid:26)(cid:27)
(cid:47)(cid:46)(cid:45)(cid:44)
(cid:31)(cid:30)(cid:29)(cid:28)
(cid:40)(cid:41)(cid:42)(cid:43)
0
1
1
0
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:72)(cid:73)(cid:74)(cid:75)
(cid:79)(cid:78)(cid:77)(cid:76)
(cid:80)(cid:81)(cid:82)(cid:83)
0
1
Publicité
2
1
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
0
3
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
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 :
– δ(q0, x) = q0 ⇔ x est correct et a autant de 0 que de 1 ;
– δ(q0, x) = q1 ⇔ 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
(cid:43)
(cid:51)
(cid:44)
(cid:44)
(cid:12)
(cid:12)
(cid:108)
(cid:108)
(cid:12)
(cid:12)
(cid:76)
(cid:76)
(cid:44)
(cid:44)
(cid:76)
(cid:76)
(cid:108)
(cid:108)
(cid:43)
(cid:51)
(cid:15)
(cid:39)
(cid:15)
(cid:15)
(cid:31)
(cid:15)
(cid:31)
(cid:43)
(cid:51)
(cid:44)
(cid:44)
(cid:12)
(cid:12)
(cid:108)
(cid:108)
(cid:12)
(cid:12)
(cid:76)
(cid:76)
(cid:47)
(cid:47)
(cid:106)
(cid:106)
4
Exercices Corrigés TD 2
TD Automates, langages et applications
– δ(q0, x) = q2 ⇔ x est correct et a un 1 de plus que de 0 ;
– δ(q0, x) = q3 ⇔ x n’est pas correct.
Si |x] = 0, alors x = ε et δ(q0, ε) = q0 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 = x0, x est correct et δ(q0, x) = q2 et donc δ(q0, y) = δ(q2, 0) = q0.
2. Si y = x1, x est correct et δ(q0, x) = q1 et donc δ(q0, y) = δ(q1, 1) = q0.
Soit |y| = n avec y correct et ayant un 1 de plus que de 0. Si y = x0, 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 = x1 et donc x a autant de 0 que de 1, donc δ(q0, x) = q0 et donc
δ(q0, y) = δ(q0, 1) = q2.
Idem si y a un 0 de plus que de 1 ou n’est pas correct.
⇐ Supposons que δ(q0, y) = q0 avec |y| ≥ 1. Si y = x0, alors δ(q0, x) = q2 (car il faut après arriver
en q0 en lisant un 0) donc par hypothèse 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 = x1 et si δ(q0, y) = q1, q2 ou q3.
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 à 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 dernière bille sort en D.
Corrigé : Un état est caractérisé par la position des trois leviers et de la sortie de la dernière bille.
L’état qi correspond a la valeur i en binaire sur l3l2l1 ou / = 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−C
1−D
0−D
1−D
(cid:63)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)
(cid:71)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)
(cid:55)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)
(cid:63)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)
(cid:103)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)
(cid:95)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)
(cid:95)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)
(cid:87)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
1−D
1−D
0−D
0−C
2
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
0
3
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
7
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
0−C
0−C
1−C
1−D
(cid:31)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)
(cid:23)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)(cid:47)
(cid:39)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)(cid:79)
(cid:31)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)(cid:62)
(cid:119)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)
(cid:127)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)
(cid:127)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)
(cid:7)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)(cid:15)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
1−D
1−C
0−C
0−C
6
1
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
5
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
En fait, chaque état est divisé en 2, suivant que la dernière bille est sorti en C ou en D. Seuls les
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
é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.
4
Université Paris-Dauphine
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard
(cid:31)
(cid:23)
(cid:31)
(cid:39)
(cid:63)
(cid:55)
(cid:63)
(cid:71)
(cid:127)
(cid:7)
(cid:127)
(cid:119)
(cid:95)
(cid:103)
(cid:95)
(cid:87)