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 1
Minimisation d’automates
Minimiser les automates des figures 1 et 2 en utilisant l’algorithme de Moore.
Figure 1 – Automate A1
0 1 2 3 4 5 6 7
ba aa ab bb aa bb bb
Figure 2 – Automate A2
0 1 2 3 4 5 6 7 8
ab bab ba ab ba bb
Pour chacun des automates des figures 1 et 2, donner les classes d’équivalence de Nérode.
Exercice 2
Division par 3 : automates minimaux
Vérifier si les automates qui reconnaissent les nombres divisibles par 3 sont minimaux.
Exercice 3
Comparaison entre expressions rationnelles et automates
Parmi les expressions rationnelles et les automates suivants, identifier ceux qui représentent le même langage.
Expressions rationnelles :
(ab*)∗
(a+b(a+b))∗
Automates :
Figure 3 – Automate A3
0 1 2 3 4 5
ba ba ab bb ab aa b
Figure 4 – Automate A4
0 1 2 3 4 5
ba bb aaabb baa
Exercice 4
Résiduels
1. Soit L1 = {b, aa, ba, aababab} et L2 = {a, b, ba, aab, bab, abab, aaba} deux ensembles de mots. Calculer les résiduels suivants :
L1−1.L2, L2−1.L1, ε−1.L1, ((a+b)∗)−1.L1 et ∅−1.L1.
2. Soit L1 et L2 deux ensembles de mots. Si ε ∈ L1, que peut-on dire sur L1−1.L2 ?
Même question si L2 = ∅.
Exercice 5
Les résiduels d’un langage et leurs automates
1. Calculer les résiduels des langages suivants :
L1 = a∗b∗
L2 = a∗ba+b∗aba
L3 = {anbn | n ≥ 0}.
2. Pour chacun des langages de l’exercice 5, dire s’ils sont reconnaissables par un automate.
Si oui, construire l’automate minimal qui reconnaît ce langage.
Vous pouvez répondre à cette question en construisant l’automate des résiduels.
Rappel : On appelle résiduels d’un langage L, les langages Rε, Ra, Rb, Raa, Rab, etc. où Ru = u−1.L et u ∈ X∗.
Exercice 6
Calcul des résiduels d’un automate
Pour chacun des automates de l’exercice 1, calculer les résiduels associés à leur langage.
Exercice 7
Déterminisme contre non-déterminisme
1. Donner un automate fini non déterministe avec n états pour le langage L = (a+b)∗a(a+b)n−2.
2. Montrer que tout automate fini déterministe reconnaissant L possède au moins 2n−1 états.
Exercice 8
Le jeu du barman aveugle
Le 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 déroule par tours. Un tour s’organise comme suit :
– Le barman retourne un ou deux verres de son choix. Pour éviter qu’il ne récupère d’informations 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 parvient à placer tous 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. pour tout a, b, c, d, les configurations (a, b, c, d), (b, c, d, a), (c, d, a, b) et (d, a, b, c) sont équivalentes), 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.
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 9
Algorithme de minimisation de Brzozowski
Soit A = (Q, Σ, δ, I, F) un automate fini non déterministe (NFA) sans transitions-ε.
Le langage à gauche Lg(q) de l’état q ∈ Q est le langage accepté par l’automate Ag(q) = (Q, Σ, δ, I, q).
Le langage à droite Ld(q) de l’état q ∈ Q est le langage accepté par l’automate Ad(q) = (Q, Σ, δ, q, F).
Soit d(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 échangeant I et F).
1. Montrer que r(A) reconnaît les miroirs des mots dans L(A) : L(r(A)) = L(A)R.
2. Montrer que le langage à gauche Lr(A)g(q) de l’état q dans r(A) est le miroir du langage à droite Ld(A)(q) de q dans A.
(Même chose pour les langages à gauche et à droite inversés.)
3. Montrer que chaque langage à droite Ld(A)d(R) associé à un état R de d(A) est l’union des langages à droite Ld(A)(r), où r ∈ R.
4. Montrer que A est déterministe si et seulement si les langages à gauche associés à ses états sont deux à deux disjoints et |I| = 1.
5. Montrer qu’un automate fini déterministe complet (DFA), dont tous les états sont accessibles, est minimal si et seulement si les langages à droite associés à ses états sont deux à deux différents.
6. Montrer que d(r(d(r(A)))) est l’automate minimal de A.
FAQ
1. Qu’est-ce que l’algorithme de Moore pour la minimisation d’automates ?
L’algorithme de Moore permet de réduire un automate fini déterministe en fusionnant les états équivalents, c’est-à-dire ceux qui ne peuvent pas être distingués par un mot du langage.
2. Comment calculer les résiduels d’un langage ?
Les résiduels d’un langage L sont obtenus en déterminant Lu = u−1.L pour chaque mot u dans l’alphabet Σ∗, où u−1 représente le préfixe inverse.
3. Pourquoi un automate non déterministe peut-il avoir moins d’états qu’un automate déterministe équivalent ?
Un automate non déterministe peut fusionner plusieurs configurations en un seul état, tandis qu’un automate déterministe doit les distinguer explicitement, ce qui augmente généralement le nombre d’états.