Théorie des langages : Exercices automate finis deterministes
Télécharger PDFChapitre 4
option informatique
Corrigé des exercices
•Automates finis déterministes �
Exercice 11. Le langage des mots contenant au moins une fois la lettrea:q 0q 1a b
a, b
2. Le langage des mots contenant au plus une fois la lettrea:q 0q 1a bb
3. Le langage des mots contenant un nombre pair de fois la lettrea:q 0q 1a bba 4. Le langage des mots admettantabapour facteur :q 0q 1q 2q 3a baba b
a, b
5. Le langage des mots admettantabapour sous-mot :q 0q 1q 2q 3a baba b
a, b �
Exercice 2Posonsn= 2p+ravecr∈{0,1}; alors :
p≡0 mod 5 =⇒n≡rmod 5p≡3 mod 5 =⇒n≡1 +rmod 5
p≡1 mod 5 =⇒n≡2 +rmod 5p≡4 mod 5 =⇒n≡3 +rmod 5
p≡2 mod 5 =⇒n≡4 +rmod 5
D’où l’automate :
http://info-llg.fr
4.2option informatiqueq 0q 1q 2q 3q 41 00 10 10 10 1
Pour lire les entiers à partir du bit de poids le plus faible, il suffit de considérer l’automate transposé, c’est-à-dire
celui obtenu en inversant l’ordre des transitions et en échangeant états initiaux et états finaux. En général, la
transposée d’un automate déterministe est non déterministe, mais l’automate ci-dessus fait exception.q 0q 1q 2q 3q 41 00 10 10 10 1 �
Exercice 3Il y a trois types de mots dans ce langage : ceux qui contiennent au moins unaet unbavant le
dernier caractère (étatq6 ), ceux qui ne contiennent que desaet qui sont de longueur au moins 2 (étatq3 ), ceux
qui ne contiennent que desbet qui sont de longueur au moins 2 (étatq5 ).q 0q 1q 2q 3q 4q 5q 6a ba ba ba b
a, ba b
a, b �
Exercice 41.Les mots deL′ sont les mots qui commencent par 1 et qui comportent au moins un 0 dans leur écriture.
D’où l’automate :
Corrigé des exercices4.3q 0q 1q 21 10 0,1
2. Les mots de E sont reconnus par l’automate :q 0q 1q 21 01 0
3.NotonsL1 le langage dénoté par01etL2 le langage dénoté par(10)∗ . AlorsS=EL1 L2 doncSest reconnu
par l’automate :q 0q 1q 2q 3q 41 01 01 10 �
Exercice 5On définit deux suites (Ri ) et (Si ) de parties de Q en posant R0 ={q0 }, S0 = F et pour touti∈N:R i+1
= Ri ∪{ q∈Q∣ ∣∣ il existe une transition d’un élément de Ri àq} Si+1 = Si ∪{ q∈Q∣ ∣∣ il existe une transition deqà un élément de Si }
Ces deux suites sont croissantes dansQfini donc sont stationnaires. Leurs limitesRetSsont atteintes dès lors
que deux termes consécutifs sont égaux et dans ce casRest l’ensemble des états accessibles etSl’ensemble
des états co-accessibles. Il suffit dès lors de supprimer les états qui n’appartiennent pas àR∩Sainsi que les
transitions dans lesquelles ces états interviennent pour obtenir l’automate émondé demandé.
Commençons par une fonction qui détermine les états accessibles en suivant l’algorithme exposé ci-dessus :
letaccessible a =
let recaux1 b =function
| []−> b
| ((i, _), j)::q when mem i b &¬mem j b−> aux1 (j::b) q
| _::q−> aux1 b q
andaux2 b =letbb = aux1 b a.Deltain
ifb = bbthenbelseaux2 bb
inaux2 [a.Start] ;;
On détermine de même les états co-accessibles :
http://info-llg.fr
4.4option informatique
letcoaccessible a =
let recaux1 c =function
| []−> c
| ((i, _), j)::q when mem j c &¬mem i c−> aux1 (i::c) q
| _::q−> aux1 c q
andaux2 c =letcc = aux1 c a.Deltain
ifc = ccthencelseaux2 cc
inaux2 a.Accept ;;
Il reste à émonder l’automate :
letemonde a =
lete = intersect (accessible a) (coaccessible a)in
let recaux =function
| []−> []
| ((i, _), j)::q whennotmem i e ||notmem j e−> aux q
| t::q−> t::(aux q)
in{Start = a.Start; Accept = intersect a.Accept e; Delta = aux a.Delta} ;;
•Automates non déterministes �
Exercice 6La déterminisation du premier automate conduit au résultat :δ ′ab {q0 }{q0 } {q0 , q1 }{q 0
, q1 }{q0 , q2 } {q0 , q1 , q2 }{q 0
, q2 }{q0 , q2 } {q0 , q1 , q2 }{q 0
, q1 , q2 }{q0 , q2 } {q0 , q1 , q2 }q ′0 q′ 1q ′2 q′ 3a ba ba bb a
La déterminisation du second automate conduit au résultat :δ ′ab {q0 }{q1 } {q2 }{q 1}{q 1
} {q0 , q2 }{q 2}{q 2
} {q0 }{q 0
, q2 }{q1 , q2 } {q0 , q2 }{q 1
, q2 }{q1 , q2 } {q0 , q2 }q ′0 q′ 1q ′2 q′ 3q ′4 ab ab ba ba ab Corrigé des exercices4.5 �
Exercice 7Seules quatre configurations sont possibles :
– les quatre verres sont tous dans le même sens (configurationq0 ) ;
– trois verres sont dans un sens et le quatrième dans l’autre sens (configurationq1 ) ;
– deux verres voisins sont dans un sens et les deux autres dans l’autre sens (configurationq2 ) ;
– deux verres opposés sont dans un sens et les deux autres dans l’autre sens (configurationq3 ).
On désigne par la lettre :
–ale fait de changer l’orientation d’un des quatre verres ;
–ble fait de changer l’orientation de deux verres voisins ;
–cle fait de changer l’orientation de deux verres opposés.
Le jeu peut alors être représenté par l’automate non déterministe suivant :q 0q 1q 2q 3aa ba bc
b, cc Sa déterminisation conduit à l’automate suivant :0123 12012
013010230212 030
a, bc ac ac ba ca
b, cb ca cb b, ca ca cb ab On constate que la succession de mouvementcbcacbcconduit nécessairement à une position gagnante pour lebarman. �
Exercice 8T(A) et doncA′ =D(T(A)) reconnait l’image miroir du langage reconnu parA, doncA′′ reconnait
le même langage que A ; il est équivalent à A.
On obtient pour A′ l’automate :
http://info-llg.fr
4.6option informatiqueq ′0 q′ 1q ′2 q′ 3q ′4 q′ 5q ′6 ab ab ba bba bba et pour A′′ l’automate :q ′′0 q′′ 1q ′′2 ab a, bb a �
Exercice 9L’automate non déterministe :q 0q 1q 2q 3q 4
a, babba a, b
se déterminise en :δ ′ab {q0 }{q0 , q1 } {q0 }{q 0
, q1 }{q0 , q1 } {q0 , q2 }{q 0
, q2 }{q0 , q1 } {q0 , q3 }{q 0
, q3 }{q0 , q1 , q4 } {q0 }{q 0
, q1 , q4 }{q0 , q1 , q4 } {q0 , q4 }{q 0
, q4 }{q0 , q1 , q4 } {q0 , q4 }q ′0 q′ 1q ′2 q′ 3q ′4 q′ 5b aa ba bab ab ab On notera que l’étatq′ 5
peut être supprimé sans changer le langage reconnu par cet automate.
L’algorithme KMP consiste à considérer les états et transitions suivants :δab εaεaaab abaabb
abbabbaεabbaaab Corrigé des exercices4.7
puis à transformer l’état acceptant (abba) en puit :ε a
ababbabbab aa ba bab a, b
•Théorème deKleene �
Exercice 10On commence par se débarrasser du symboleε: l’expression rationnelle est équivalente à(a+c) ∗
abb+(a+c)∗ . On la linéarise pour obtenir un langage local :(c1 +c2 )∗ c3 c4 c5 +(c6 +c7 )∗ , avecP={c1 , c2 , c3 , c6 , c7 },
S ={c5 , c6 , c7 }et F ={c2 1
, c2 2
, c1 c2 , c2 c1 , c1 c3 , c2 c3 , c3 c4 , c4 c5 , c2 6
, c2 7
, c6 c7 , c7 c6 }.
On déduit de l’automate local qui en résulte l’automate deGlushkovde l’expression rationnelle en supprimant
le marquage des transitions :c 0c 3c 4c 5c 2c 1c 6c 7a ca ac ca aa ac bb ca ac On notera que puisqueεappartient au langagec0 est un état acceptant. Sa déterminisation fournit l’automate
suivant :q 0q 1q 2q 3q 4a ca cb ca b �
Exercice 11L’automate suivant reconnait le langage L ={ m∈Σ∗ ∣∣ ∣|m| a
≡0 mod 3} :
http://info-llg.fr
4.8option informatiqueq 0q 1q 2a ba ba b
On lui applique l’algorithme d’élimination des états en éliminant successivementq2 ,q1 etq0 :i q0 fq 1q 2a bε ab ab εi q0 fq 1a bε ab∗ ab εi q0 fb+ab ∗ab ∗a εεi f(b+ab ∗ab ∗a) ∗
L est donc dénoté par (b+ab∗ ab∗ a)∗ . �
Exercice 12L’automate suivant reconnait le langage L :q 0q 1q 2q 3a ab ab a
On le rend complet en ajoutant un état puit :q 0q 1q 2q 3q 4a ba ba ba b
a, b
En inversant les états acceptants on obtient un automate qui reconnaitL :
Corrigé des exercices4.9q 0q 1q 2q 3q 4a ba ba ba b
a, b �
Exercice 13SiL1 etL2 sont deux langages reconnus par des automatesA1 etA2 nous savons calculer les
automates reconnaissant l’intersection et le complémentaire donc des automates reconnaissantL1 \L2 etL2 \L1 .
Il reste à utiliser l’équivalence : L1 = L2 ⇐⇒(L1 \L2 =∅et L2 \L1 =∅) pour conclure. �
Exercice 14Considérons un automate fini déterministeA= (Σ,Q, q0 ,F,δ) qui reconnaitL, notonsAc(respec-
tivementCo) l’ensemble des états accessibles (respectivement co-accessibles) et considérons les trois automates :A p
= (Σ,Q, q0 ,Co,δ),As = (Σ,Q,Ac,F,δ),Af = (Σ,Q,Ac,Co,δ)
(les deux derniers sont non déterministes).AlorsA p
reconnaitpref(L),Af reconnaitsuff(L),Af reconnaitfact(L) (on peut aussi observer quefact(L) =
pref(suff(L)). �
Exercice 15SoitA= (Σ,Q, q0 ,F,δ) un automate qui reconnaitL. Pour toutq∈Qon noteIq l’ensemble des
mots qui étiquètent un chemin deq0 àqetFq l’ensemble des mots qui étiquètent un chemin deqà l’un des états
finaux deF. Ces deux langages sont respectivement reconnus par(Σ,Q, q0 ,{q},δ) et(Σ,Q, q,F,δ) donc rationnels.
L’égalité√ L =⋃ q∈QI q∩F q
prouve alors que√ L est aussi rationnel. �
Exercice 16SoitA= (Σ,Q, q0 ,F,δ) un automate qui reconnait le langageL. On noteIl’ensemble des états
accessibles à partir deq0 en suivant un chemin étiqueté par un mot deK. On considère alors l’automate (non
déterministe) A′ = (Σ,Q,I,F,δ) ; nous allons montrer que A′ reconnait K−1 L.
Considérons un motv∈K−1 Letu∈Ktel queuv∈L. Puisqueuv∈Lle cheminq0 uv qf mène à un état
acceptantqf ∈F. Ce dernier se décompose en deux cheminsq0 u q
v qf avecq∈Ice qui montre quevétiquète
un chemin menant d’un étatq∈I à un étatqf ∈F.vest donc reconnu par A′ .
Réciproquement, sivest reconnu parA′ il existeq∈I,qf ∈Fet un cheminq
v qf étiqueté parv. Par définition
deIil existeu∈Ket un cheminq0 u q
étiqueté paruce qui prouve queuvest reconnu parA, donc queuv∈L.
•Lemme de l’étoile �
Exercice 17Supposons le lemme de l’étoile vérifié par le langageL1 et posonsu=ε,v=ak etw=bk+1 . Le
motuvwappartient àL1 doncvse factorise env=ak 1a k2 ak 3aveck 2
>1 et pour toutn∈N,uv1 vn+1 2v 3w =a k+nk2 bk+1 ∈L1 , ce qui est absurde.
Supposons le lemme de l’étoile vérifié pour le langageL2 et posonsu=ak ,v=bk ,w=ε. Alors il existek2 >1 tel
que pour toutn∈N,ak bk+nk 2∈L 2
, ce qui est absurde.
Supposons le lemme de l’étoile vérifié pour le langageL3 et considérons un entier premierptel quep>k. Alorsa p
se factorise sous la formeak 1a k2 ak 3aveck 2
>1 et pour toutn∈N,ap+nk 2∈L 3
. En particulier, pourn=ple
nombrep+pk2 doit être premier, ce qui est absurde. �
Exercice 18Si le langage deDickétait rationnel il existerait un automate reconnaissant les mots de la formea nb n
; or nous avons vu que dans ce cas il existek2 >1 tel que le motan bn+k 2
soit reconnu, et ce dernier mot
n’est pas un mot deDick.
http://info-llg.fr
4.10option informatique
Pour toutk∈Nle mot(1+(1+(1+(...1))...)(comportantkparenthèses ouvrantes et fermantes) appartient
au langageCaml; en posantu=(1+(1+(1+(...1,v=))...)etw=εle second lemme de l’étoile conduit à
une absurdité. �
Exercice 19SupposonsLrationnel ; d’après le second lemme de l’étoile il existe un entierktel que pour tout
palindromem=uvwtel que|v|>kse factorise sous la formem=uv1 v2 v3 wavec|v2 |>1,|v1 v2 |6ket∀n∈N,uv 1v n2 v3 west un palindrome. En considérant le motm=ak bak avecu=ε,v=ak etw=bak on prouve l’existence
d’un entierp >0 tel que pour toutn∈N,ak+np bak doive être un palindrome, ce qui est absurde. �
Exercice 20SupposonsLrationnel et notonskl’entier qui intervient dans la première version du lemme
de l’étoile. Si la conjecture est vraie il existep>ktel que2p −1 soit un nombre premier et dans ce cas le mot1 p
appartient àL. D’après le lemme de l’étoile ce mot se factorise sous la formeuvwavec|v|>1 et pour toutn∈N,uv n
w∈L. En posantv= 1j on prouve que pour toutn∈Nle mot1p+nj appartient àL, autrement dit que2 p+nj
−1 est premier. Mais en prenantn=pon aboutit à une absurdité car2p(j+1) −1 est divisible par2j+1 −1>3.