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 :
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 ´etat repr´esente la congruence modulo 5.
Si x ≡ b [5], alors x0 ≡ 2b [5] et x1 ≡ 2b + 1 [5].
Universit´e 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)
Advertisement
(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)
(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´es 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´eterministe 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´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
a,b
2
Pour reconnaˆıtre les mots ne contenant pas ab, il faut prendre son compl´ementaire, c’est
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
-`a-dire transformer chaque ´etat 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
Advertisement
2. L’automate suivant reconnaˆıt les mots contenant ab et commen¸cant 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´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 :
(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´e Paris-Dauphine
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)
Advertisement
(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´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 :
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´e : 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´e :
{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´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.
(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
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´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 :
– δ(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´e 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)
Advertisement
(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´es 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´efixe 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`es arriver
en q0 en lisant un 0) donc par hypoth`ese 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 = x1 et si δ(q0, y) = q1, q2 ou q3.
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 derni`ere bille sort en D.
Corrig´e : Un ´etat est caract´eris´e par la position des trois leviers et de la sortie de la derni`ere bille.
L’´etat qi correspond a la valeur i en binaire sur l3l2l1 ou / = 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−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 ´etat est divis´e en 2, suivant que la derni`ere 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)
´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.
4
Universit´e 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)