TD Automates, langages et applications
Exercices Corrigés TD 5
1
Automates, Langages et Applications - TD 5
1 Lemme de pompage
Exercice 1 Les langages suivants sont-ils réguliers?
– L1 = {02n/n ≥ 1}
– L2 = {02n/n ≥ 1}
– L3 = {0n1n/n ≥ 1}
– L4(n) = {x ∈ {0, 1}∗/n0(x) ≡ n1(x) [n]} où n0(x) (resp. n1(x)) est égal au nombre de 0 (resp.
de 1) dans l’écriture de x.
– L5 = {x ∈ {0, 1}∗/x n’a pas 3 zéros consécutifs}
– L6 = {0n/n premier}
Corrigé :
1. L1 = 00(00)∗. C’est donc un langage régulier.
2. Supposons que L2 soit régulier. Soit n ≥ 1. Alors, le lemme de pompage nous dit que, comme
z = 02n ∈ L2 et 2n > n, on peut écrire z = uvw avec |v| ≤ n tel que z(cid:48) = uv2w ∈ L2. Or
|z(cid:48)| = |uv2w| ≤ 2n + n. Mais 2n + n < 2n+1 donc on ne peut pas avoir z(cid:48) ∈ L2. C’est une
contradiction, donc L2 n’est pas régulier.
3. Supposons que L3 soit régulier. Soit n ≥ 1. On applique le lemme de pompage avec z = 0n1n.
Donc z = uvw et z(cid:48) = uv2w doit être dans L3. Donc v a autant de 0 que de 1 ; mais alors
v2 = 0i1i0i1i et z(cid:48) ne pourrait pas être dans L3, sauf si i = 0, ce qui est impossible. C’est donc
une contradiction et L3 n’est pas régulier.
4. Soit n > 0, L4 est reconnu par l’automate suivant où chaque état représente n0(x)−n1(x) mod n.
1
0 (cid:44)
1
1
0
(cid:71)(cid:70)
0 (cid:44)
1
2
0
1
. . .
0
(cid:87)(cid:86)(cid:85)(cid:84)
(cid:80)(cid:81)(cid:82)(cid:83)
5. L5 est régulier car reconnu par l’automate :
(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)
(cid:64)(cid:65)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
0 (cid:46)
1
n − 2
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:95)(cid:94)(cid:93)(cid:92)
0 (cid:45)
1
n − 1
(cid:69)(cid:68)
(cid:95)(cid:94)(cid:93)(cid:92)
Publicité
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:66)(cid:67)
1
0
1
0
1
0
2
6. Supposons que L6 soit régulier et soit n ≥ 1. Prenons un mot z = 0p avec |z| > n et p premier
(il existe une infinité de nombres premiers, donc on peut toujours trouver un tel p). On applique
le lemme de pompage, donc z = uvw avec 1 ≤ |v| ≤ n.
(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)
(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)
Soit z(cid:48) = uvp+1w. |z(cid:48)| = |u| + (p + 1)|v| + |w| = p + |v|p. |z(cid:48)| est donc un multiple de p et
n’est pas premier. z(cid:48) ne peut donc pas appartenir à L6, ce qui est une contradiction. L6 n’est
donc pas régulier.
Exercice 2 On definit l’inverse d’une chaˆıne w = a1a2...an comme étant la chaˆıne écrite à l’envers,
c’est-à-dire anan−1...a1, que l’on notera wR.
1. Soit un langage régulier L reconnu par un automate M . Donner une méthode permettant de
construire à partir de M un automate M (cid:48) reconnaissant LR.
Université Paris-Dauphine
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard
(cid:43)
(cid:51)
(cid:44)
(cid:15)
(cid:15)
(cid:44)
(cid:108)
(cid:108)
(cid:108)
(cid:108)
(cid:43)
(cid:43)
(cid:108)
(cid:108)
(cid:46)
(cid:107)
(cid:107)
(cid:45)
(cid:109)
(cid:109)
(cid:15)
(cid:15)
Publicité
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:9)
(cid:9)
(cid:47)
(cid:47)
(cid:108)
(cid:108)
(cid:105)
(cid:105)
2
Exercices Corrigés TD 5
TD Automates, langages et applications
2. Les palindromes sont les mots qui se lisent de la même maniere a l’endroit et à l’envers (quel
est le plus long que vous connaissiez ?). Autrement dit, les mots tels que w = wR. Montrer que
le langage des palindromes n’est pas régulier.
Corrigé :
1. La réponse immédiate est évidemment que pour construire M (cid:48), il suffit d’inverser toutes les
transitions ainsi que état de départ et état final... sauf qu’un automate peut avoir plusieurs états
finaux ! Il faut donc rajouter un état supplémentaire qui sera le nouvel état de départ et d’où
partent des (cid:15)-transitions vers tous les états finaux de M . Ces anciens états finaux ne le sont bien
sûr plus ; il n’y a qu’un état final, l’état de départ de M .
Voici M :
...
0
(cid:63)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)
(cid:31)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
...
Et voici M (cid:48) :
...
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)
(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)
(cid:95)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)
...
...
...
f1
(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)
f2
(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)
...
...
Publicité
...
f1
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:95)(cid:94)(cid:93)(cid:92)
(cid:15)
(cid:95)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)(cid:63)
(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)(cid:127)
(cid:15)
q
(cid:80)(cid:81)(cid:82)(cid:83)
(cid:87)(cid:86)(cid:85)(cid:84)
f2
2. (cid:40)(cid:40) élu par cette crapule (cid:41)(cid:41), (cid:40)(cid:40) Ésope reste ici et se repose (cid:41)(cid:41), (cid:40)(cid:40) Et la marine va venir à Malte (cid:41)(cid:41), ou
(cid:88)(cid:89)(cid:90)(cid:91)
(cid:95)(cid:94)(cid:93)(cid:92)
(cid:40)(cid:40) engage le jeu que je le gagne (cid:41)(cid:41) sont des palindromes classiques.
Supposons que L soit régulier (sur l’alphabet {0, 1} pour simplifier). Soit n ≥ 1. On applique
le lemme de pompage avec z = 0n10n. z est bien un palindrome, donc est dans L. On peut donc
décomposer z = uvw avec |uv| ≤ n et |v| ≥ 1. D’après le lemme, z(cid:48) = uv2w doit être dans L.
Mais comme |uv| ≤ n, aussi bien u que v sont composés uniquement de 0. On peut alors écrire
z(cid:48) = 0n0|v|10n et comme |v| ≥ 1, z(cid:48) n’est pas un palindrome. C’est donc une contradiction et L
n’est pas régulier.
Université Paris-Dauphine
M1 Master MIAGE&D - 2009/2010
B, Escoffier, E. Lazard
(cid:15)
(cid:15)
(cid:47)
(cid:47)
(cid:43)
(cid:51)
(cid:47)
(cid:47)
(cid:63)
(cid:31)
(cid:79)
(cid:79)
(cid:47)
(cid:47)
(cid:127)
(cid:111)
(cid:111)
(cid:79)
(cid:79)
(cid:15)
(cid:15)
(cid:111)
(cid:111)
(cid:107)
(cid:115)
(cid:95)
(cid:127)
(cid:95)
(cid:111)
(cid:111)