Théorie des langages : Td 3 minimisation des automates et résiduels
Télécharger PDFFeuille 3 - Minimisation des automates et Résiduels
Informatique Théorique 2 - Unité J1INPW11
Licence 3 - Université Bordeaux 1
Exercice 1Minimisation dťautomates
Minimiser les automates des figures 1 et 2 en utilisant l’algorithme de Moore.0 12345 67 ba aa ab bb aa aa bb bb Figure1 – AutomateA1 12345678 ab bab ba ab ba bb Figure2 – AutomateA2 Pour chacun des automates des figures 1 et 2, donner les classes d’équivalence de Nérode.
Exercice 2Division par 3 : automates minimaux
Vérifier si les automates qui reconnaissent les nombres divisibles par 3 (exercice 2 de la
feuille 2) sont minimaux.
Exercice 3Comparer entre eux des expressions rationnelles et des automates
Parmi les expressions rationnelles et les automates suivants dire quels sont les automates
et les expressions rationnelles qui représentent le même language.(ab ∗
a+b(a+b))∗ 012345 ba ba ab bb ab aa b
Figure3 – AutomateA3 (ab+b(a+b))∗ 012345 ba bb aaabb baa Figure4 – AutomateA4 1
Exercice 4Résiduels
1. SoitL1 ={b, aa, ba, aababab}etL2 ={a, b, ba, aab, bab, abab, aaba}deux ensembles de
mots. Calculer les résiduels suivants :L−1 1.L 2,L −12 .L1 ,ǫ−1 .L1 ,[(a+b)∗ ]−1 .L1 et∅−1 .L1 .
2. SoitL1 etL2 deux ensembles de mots. Siǫ∈L1 , que peut-on dire surL−1 1.L 2
? Même
question siL2 =∅.
Exercice 5Les résiduels d’un language et leurs automates
1. Calculer les résiduels des languages suivantsL1 =a∗ b∗ ,L2 =a∗ ba+b∗ abaetL3 ={a nb n|n≥0}. 2. Pour chacun des languages de l’exercice 5, dire si ils sontreconnaissables par un au-
tomate. Si oui, construire l’automate minimal qui reconnait ce language. Vous pouvez
répondre à cette question en construisant l’automate des résiduels.
Rappel : on appelle résiduels d’un languageL, les languagesRǫ ,Ra ,Rb ,Raa ,Rab , etc... oùR u=u −1.Letu∈X ∗.
Exercice 6Calcul des résiduels d’un automate
Pour chacun des automates de l’exercice 1, calculer les résiduels associés à leur language.
Exercice 7Déterminisme contre non-determinisme
1. Donnez un automate fini non déterministe avecnétats pour le languageL= (a+b) ∗a(a+b) n−2
2. Montrez que tout automate fini déterministe reconnaissantLpossède au moins2n−1 états.
Exercice 8Le jeu du barman aveugle consiste à poser quatre verres en cercle sur un plateau. Les verres
peuvent être retournés ou non. Le but du barman est de s’arranger pour que tous les verres
soient dans le même sens, mais sans les voir. Le but de son adversaire est qu’il n’y arrive pas.
Le jeu se joue par tours. Un tour s’organise comme suit :
– Le barman retourne un ou deux verres de son choix. Pour qu’ilne récupère pas d’infor-
mation en les touchant on lui met des gants de boxe ;
– L’adversaire fait faire un nombre quelconque de quarts de tours au plateau.
Si le barman place les verres dans le même sens, le jeu s’arrête.
On appelle configuration du plateau à un instant donné la position des verres à cet
instant. En numérotant les verres dans l’ordre, on peut représenter une configuration par
(haut,bas,bas,haut).
1. En remarquant que pour le barman, les configurations obtenues par rotation du plateau
sont équivalentes (i.e.∀a, b, c, d(a, b, c, d),(b, c, d, a),(c, d, a, b)et(d, a, b, c)sont équi-
valents) montrer qu’il y a quatre configurations possibles du plateau et qu’il y a trois
actions possibles pour le barman.
2. Représenter les exécutions possibles du jeu par un automate non déterministe.
3. Déterminiser l’automate.2 4. En remarquant qu’obtenir une stratégie gagnante pour le barman revient à trouver une
série d’actions qui, quelle que soit la configuration de départ, passe par un état final,
aider le barman à gagner.
Exercice 9algorithme de minimisation de Brzozowski
SoitA= (Q,Σ, δ, I, F)un NFA sans transitions-ε. Le langage à gaucheLA g
(q)de l’état
q∈Qest le langage accepté par l’automateAg (q) = (Q,Σ, δ, I, q). Le langage à droiteLA d(q) de l’étatq∈Qest le langage accepté par l’automateAd (q) = (Q,Σ, δ, q, F).
Soitd(A)l’automate des parties associé àA(en ne gardant que les états accessibles). Soit
r(A)l’automate miroir associé àA(obtenu en renversant les flèches et en échangeantIetF).
1. Montrer quer(A)reconnaît les miroirs de mots dansL(A):L(r(A)) =L(A)R .
2. Montrer que le langage à gaucheLr(A) g
(q)de l’étatqdansr(A)est le miroir du langage
à droiteLA d
(q)deqdansA. (Pareil pour gauche et droite inversés.)
3. Montrer que chaque langage à droiteLd(A) d
(R)associé à un étatRded(A)est l’union
des langages à droiteLA d
(r), oùr∈R.
4. Montrer queAest déterministe ssi les langages à gauche associés à ses états sont deux
à deux disjoints et|I|= 1.
5. Montrer qu’un DFA complet, dont tous les états sont accessibles, est minimal ssi les
langages à droite associés à ses états sont deux à deux différents.
6. Montrer qued(r(d(r(A))))est l’automate minimal deA.
3