Théorie des langages : Exercices automate finis deterministes
Télécharger PDFCorrigé des exercices sur les automates finis (option informatique)
Automates finis déterministes
Exercice 11. Le langage des mots contenant au moins une fois la lettre a :
q0 → q1 sur a
q0 → q0 sur b
q1 est un état final.
2. Le langage des mots contenant au plus une fois la lettre a :
q0 → q1 sur a
q0 → q0 sur b
q1 → q2 sur a
q1 → q1 sur b
q2 est un état final.
3. Le langage des mots contenant un nombre pair de fois la lettre a :
q0 → q1 sur a
q0 → q0 sur b
q1 → q2 sur a
q1 → q1 sur b
q2 → q3 sur a
q2 → q2 sur b
q3 → q0 sur a
q3 → q3 sur b
q0 est un état final.
4. Le langage des mots admettant aba comme facteur :
q0 → q1 sur a
q0 → q0 sur b
q1 → q2 sur b
q1 → q1 sur a
q2 → q3 sur a
q2 → q2 sur b
q3 est un état final.
5. Le langage des mots admettant aba comme sous-mot :
q0 → q1 sur a
q0 → q0 sur b
q1 → q2 sur b
q1 → q1 sur a
q2 → q3 sur a
q2 → q2 sur b
q3 est un état final.
Exercice 2
Posons n = 2p + r avec r ∈ {0, 1} ; alors :
p ≡ 0 mod 5 ⇒ n ≡ r mod 5
p ≡ 3 mod 5 ⇒ n ≡ 1 + r mod 5
p ≡ 1 mod 5 ⇒ n ≡ 2 + r mod 5
p ≡ 4 mod 5 ⇒ n ≡ 3 + r mod 5
p ≡ 2 mod 5 ⇒ n ≡ 4 + r mod 5
L’automate correspondant est :
q0 → q1 sur 1
q0 → q0 sur 0
q1 → q2 sur 0
q1 → q1 sur 1
q2 → q3 sur 1
q2 → q2 sur 0
q3 → q4 sur 0
q3 → q3 sur 1
q4 → q0 sur 1
q4 → q4 sur 0
q0 est un état final.
Exercice 3
Il y a trois types de mots dans ce langage :
1. Ceux qui contiennent au moins une a et une b avant le dernier caractère (état q6) :
q0 → q1 sur a
q0 → q0 sur b
q1 → q2 sur b
q1 → q1 sur a
q2 → q3 sur a
q2 → q2 sur b
q3 → q6 sur a
q3 → q3 sur b
q6 est un état final.
2. Ceux qui ne contiennent que des a et sont de longueur au moins 2 (état q3) :
q0 → q1 sur a
q0 → q0 sur b
q1 → q2 sur b
q1 → q1 sur a
q2 → q3 sur a
q2 → q2 sur b
q3 est un état final.
3. Ceux qui ne contiennent que des b et sont de longueur au moins 2 (état q5) :
q0 → q1 sur a
q0 → q0 sur b
q1 → q2 sur b
q1 → q1 sur a
q2 → q4 sur a
q2 → q2 sur b
q4 → q5 sur b
q4 → q4 sur a
q5 est un état final.
Exercice 4
1. Les mots de L' sont ceux qui commencent par 1 et qui comportent au moins un 0 dans leur écriture.
L’automate correspondant est :
q0 → q1 sur 1
q0 → q2 sur 0
q1 → q1 sur 1
q1 → q2 sur 0
q2 est un état final.
2. Les mots de E sont reconnus par l’automate :
q0 → q1 sur 1
q0 → q2 sur 0
q1 → q1 sur 0
q1 → q2 sur 1
q2 est un état final.
3. Soit L1 le langage dénoté par 01 et L2 le langage dénoté par (10)*. Alors S = L1 ∪ L2, donc S est reconnu par l’automate :
q0 → q1 sur 0
q0 → q2 sur 1
q1 → q3 sur 1
q2 → q4 sur 0
q3 → q3 sur 0
q3 → q4 sur 1
q4 → q4 sur 0
q4 → q4 sur 1
q3 et q4 sont des états finaux.
Exercice 5
On définit deux suites (Ri) et (Si) de parties de Q en posant :
R0 = {q0}, S0 = F
Pour tout i ∈ N :
Ri+1 = Ri ∪ {q ∈ Q | il existe une transition d’un élément de Ri à q}
Si+1 = Si ∪ {q ∈ Q | il existe une transition de q à un élément de Si}
Ces suites sont croissantes dans Q fini, donc stationnaires. Leurs limites R et S sont atteintes dès lors que deux termes consécutifs sont égaux.
R est l’ensemble des états accessibles et S l’ensemble des états co-accessibles.
Pour émonder l’automate, il suffit de supprimer les états qui n’appartiennent pas à R ∩ S ainsi que les transitions les impliquant.
Automates non déterministes
Exercice 6La déterminisation du premier automate conduit à :
q0' → q1' sur a
q0' → q0' sur b
q1' → q2' sur a
q1' → q1' sur b
q2' → q3' sur b
q2' → q2' sur a
q3' est un état final.
La déterminisation du second automate conduit à :
q0' → q1' sur a
q0' → q0' sur b
q1' → q2' sur b
q1' → q1' sur a
q2' → q3' sur a
q2' → q4' sur b
q3' → q5' sur a
q3' → q5' sur b
q4' → q5' sur a
q4' → q5' sur b
q5' est un état final.
Exercice 7
Les quatre configurations possibles sont :
– q0 : les quatre verres sont tous dans le même sens ;
– q1 : trois verres sont dans un sens et le quatrième dans l’autre sens ;
– q2 : deux verres voisins sont dans un sens et les deux autres dans l’autre sens ;
– q3 : deux verres opposés sont dans un sens et les deux autres dans l’autre sens.
L’automate non déterministe est :
q0 → q1 sur a
q0 → q2 sur b
q0 → q3 sur c
q1 → q2 sur b
q1 → q3 sur c
q2 → q1 sur a
q2 → q3 sur c
q3 → q1 sur a
q3 → q2 sur b
Sa déterminisation conduit à :
q0' → q1' sur a
q0' → q2' sur b
q0' → q3' sur c
q1' → q2' sur a
q1' → q3' sur b
q2' → q1' sur a
q2' → q3' sur c
q3' → q1' sur a
q3' → q2' sur b
q3' → q0' sur c
Exercice 8
L’automate A' reconnaît l’image miroir du langage reconnu par A.
L’automate A'' reconnaît le même langage que A et est équivalent à A.
L’automate A' est :
q0' → q1' sur a
q0' → q2' sur b
q1' → q3' sur a
q1' → q4' sur b
q2' → q3' sur b
q2' → q4' sur a
q3' est un état final.
L’automate A'' est :
q0'' → q1'' sur a
q0'' → q2'' sur b
q1'' → q0'' sur a
q1'' → q3'' sur b
q2'' → q3'' sur a
q2'' → q0'' sur b
q3'' est un état final.
Exercice 9
L’automate non déterministe :
q0 → q1 sur a
q0 → q0 sur b
q1 → q2 sur b
q1 → q1 sur a
q2 → q3 sur a
q2 → q2 sur b
q3 → q4 sur b
q3 → q3 sur a
q4 est un état final.
Sa déterminisation donne :
q0' → q1' sur a
q0' → q0' sur b
q1' → q2' sur b
q1' → q1' sur a
q2' → q3' sur a
q2' → q2' sur b
q3' → q4' sur b
q3' → q4' sur a
q4' → q4' sur a
q4' → q4' sur b
q0' et q4' sont des états finaux.
Théorème de Kleene
Exercice 10L’expression rationnelle est équivalente à (a + c)*abb + (a + c)*.
On la linéarise pour obtenir un langage local : (c1