Université de la Manouba
Ecole supérieur de commerce
TD N°3 : Théories des Langages
Exercice 1 :
Pour chacun des langages suivants, construire un automate d’états finis qui l’accepte :
Exercice 2 :
Etant donné les automates d’états finis non déterministes :
A = (Q, VT, δ, S0, F) où:
Q = {S0 , S1 , S2}; VT ={0, 1} ; F = {S1 , S2} ; S0 état initial
δ = { (0 , S0 , S0) ; (0 , S0 , S1) ; (0 , S1 , S1) ; (1 , S1 , S2) ; (1 , S0 , S2) ; (1 , S2 , S2) ; (1 ,
S2 , S0) } ;
B = (Q, VT, δ, S0, F) où
Q= {S0 , S1 , S2 , S3}; VT = {a, b}; F = {S1} ; S0 état initial
δ = { (a , S0 , S0) ; (a , S0 , S1) ; (b , S0 , S2) ; (b , S1 , S2) ; (a , S1 , S3) ; (a , S2 , S2) ; (b ,
S2 , S1) ; (b , S2 , S3) ; (a , S3 , S1) ; (b , S3 , S2) } ;
1. Dessiner le diagramme graphique représentant chacun des automates A et B.
2. Déterminer une grammaire régulière à droite équivalente à chacun des automates A et B.
3. Trouver un automate d’états finis déterministe équivalent à A et à B.
Exercice 3 :
Construire un automate fini déterministe qui accepte les mots sur X = {a, b} reconnus par
l’automate fini non déterministe suivant :
1
Exercice 4 :
Soit l’expression régulière (a|b)∗abb sur l’alphabet X = {a, b}.
1. Construire un automate fini non déterministe qui reconnaît (a |b)∗abb
2. Rendre déterministe l’automate précédent. Est-il optimal ? si non l’optimiser.
Exercice 5 :
Soient les deux automates M1 et M2 suivants, définis sur Σ = {a, b} :
Automate M1
Automate M2
2
1. Ces automates sont-ils déterministes ? Justifier.
2. Donner la définition formelle de chacun des deux automates.
3. En utilisant le théorème d’Arden, donner les expressions régulières équivalentes,
respectivement, aux automates M1 et M2.
Exercice 6 :
