Vous trouverez sur cette page des exercices corrigés sur : optimisation des automates, la déterminisation et la minimisation.
Déterminisation
Exercice 1
Déterminiser les automates suivants :
Exercice 2
On considère l’alphabet A constitué des lettres de l’alphabet de la langue française et le langage L = { w ∈ A* / w se termine par man}. Trouver un automate déterministe qui engendre L.
Représentons par x toutes les lettres qui ne sont pas {a,m,n}. L’automate doit reconnaitre les mots [a-z ; A-Z]*man. Construisons un automate indéterministe avec l’algorithme de Thompson (ici nous remarquons que les epsilons transitions ne sont pas utiles). L’automate est le suivant :
Après déterminisation nous obtenons l’automate suivant :
Exercice 3
Soit L le langage accepté par l’automate A ci-dessous :
Trouver une grammaire régulière engendrant L. Trouver une expression régulière dénotant L. Trouver un automate déterministe acceptant L.
Voici les productions de grammaire obtenues directement à partir de l’automate : P → aP, P → aQ, Q → bP, Q → R, R → bR, R → cQ, R → bP, R → epsilon. Les non-terminaux (donc les nœuds de l’automate) de la grammaire sont {P,Q,R}, le symbole initial est P.
En dénotant avec Xp, Xq, Xr les langages acceptés à partir des états P, Q et R respectivement, le système d’équations pour ces langages est :
Attention, une récursion d’un non-terminal donnera une étoile, et une distribution avec des non-terminaux provoquera une concaténation !
On déterminise l’automate :
Exercice 4
On considère la grammaire régulière G = (Γ,Σ,S,Π) avec Γ = {S,P,R},Σ= {a,b} et Π = {S → P,P → baR,P → aS,R → bb,R → aP}. Trouver une expression régulière pour ce langage. Construire un automate A acceptant le langage défini par la grammaire G. Donner explicitement A sous la forme (Q,Σ,q0,F,∆). Trouver un automate déterministe acceptant ce langage.
On utilise les mêmes lettres S, P et R pour les langages accepté à partir des états S, P et R. Ces langages satisfont le système d’équations:
La première équation donne S = P, en substituant les expressions pour S et R dans la deuxième équation on obtient P = aP + ba(aP + bb) ce qui est équivalent à P = (a + baa)P + babb. Ici, P agit comme un état de départ car il existe que une espilon transition entre S et P.
On résout cette dernière équation: P = (a+baa)∗babb, d’où L(A) = S = P = (a+baa)∗babb.
Partir du l’automate de Thompson pour arriver à :
En déterminisant l’automate A on obtient B (pour plus de faciliter, il est parfois utile de mettre un état poubelle prenant les interactions sans nœuds d’arrivé):
Exercice 5
Construire un automate fini déterministe correspondant à chaque automate ci-dessous, et calculez une expression régulière pour le langage accepté à l’aide de la grammaire associée :
Exercice 6
Un barman aveugle joue au jeu suivant avec un client : il a devant lui un plateau sur lequel sont disposés quatre verres formant un carré. Chacun de ces verres peut être retourné ou non, sans que le barman ne le sache. Le but de ce dernier est de s’arranger pour que tous les verres soient tournés dans le même sens. Pour ce faire, il peut à chaque tour choisir l’une des trois actions suivantes : $
- tourner l’un des verres
- tourner deux verres voisins
- tourner deux verres opposés
mais pour corser la difficulté, le client peut tourner le plateau d’un nombre quelconque de quart de tours entre chacune des actions du barman. Le jeu s’arrête dès qu’une des deux positions gagnantes est atteinte.
Montrer qu’on peut restreindre à quatre le nombre de configurations différentes, puis représenter les actions possibles du jeu par un automate non déterministe.
Déterminiser cet automate et en déduire une stratégie gagnante pour le bar.
Seules quatre configurations sont possibles :
-les quatre verres sont tous dans le même sens (configuration q0)
-trois verres sont dans un sens et le quatrième dans l’autre sens (configuration q1)
-deux verres voisins sont dans un sens et les deux autres dans l’autre sens (configuration q2)
-deux verres opposés sont dans un sens et les deux autres dans l’autre sens (configuration q3).
On désigne par la lettre :
-a le fait de changer l’orientation d’un des quatre verres
-b le fait de changer l’orientation de deux verres voisins
-c le fait de changer l’orientation de deux verres opposés.
Le jeu peut alors être représenté par l’automate non déterministe suivant :
Sa déterminisation conduit à l’automate suivant :
On constate que le mot reconnu cbcacbc conduit à une position gagnante pour le barman.
Minimisation
Exercice 7
On considère l’automate A = ({a, b}, {1, 2, 3}, ∆, {1}, {1}) suivant :
Donnez la table décrivant ∆. Le mot baabab est-il accepté par l’automate A (vérifier en déroulant la grammaire que vous aurez préalablement écrite)? Donnez l’automate fini déterministe minimal qui reconnait le même langage que A.
∆ = {(1, a, 2),(1, b, 1),(1, b, 3),(2, a, 1),(2, a, 3),(3, b, 1)}
baabab n’est pas accepté par l’automate. On peut ajouter un puits, noté #, à l’automate pour le rendre complet. L’arbre de lecture est alors le suivant :
Aucune feuille ne correspond à un état final, notons que toutes les feuilles finissent dans le puits.
L’automate déterministe :
Les états {1} et {1,3} ont les mêmes règles. On trouve donc l’automate minimal :
Exercice 8
Parmi les expressions rationnelles et les automates suivants dire quels sont les automates et les expressions rationnelles qui représentent le même langage :
On souhaite comparer les quatre langages. On calcule l’automate minimal de chaque langage. Il suffira ensuite de comparer ces automates. En effet l’automate minimal est un objet canonique ne dépendant que du langage, deux langages sont donc égaux si ils ont le même automate minimal (modulo renommage des états).
1 – Expression Rationnelle (ab∗a + b(a + b))∗ . On commence par construire un automate par une méthode au choix :
On souhaite maintenant construire l’automate minimal du langage. Pour cela il faut d’abord déterminiser puis minimiser l’automate ci-dessus. Par chance on a déjà un automate déterministe, on peut donc directement passer à l’algorithme de minimisation qui nous donne le résultat suivant :
2 – Expression Rationnelle (ab + b(a + b))∗ . On commence par construire un automate par la méthode de Glushkov :
De même l’automate est déjà déterministe. Après minimisation nous avons l’automate suivant :
3 – Pour minimiser A3, on doit d’abord le déterminiser. Voici le résultat de l’algorithme de déterminisation :
Et après minimisation :
4 – L’automate est déjà déterministe, après minimisation nous obtenons :
Maintenant que nous avons construit l’automate minimal pour chacun des quatre langages, on peut les comparer. On constate que modulo renommage des états les langages de A3 et (ab + b(a + b))∗ ont le même automate minimal et sont donc égaux. Il en va de même pour les langages de A4 et (ab∗a + b(a + b))∗ .
Exercice 9
Soit Σ = {a,b}, on considère deux langages suivants : L, le langage formé de tous les mots de Σ∗ contenant aba; M, le langage défini par l’expression régulière (b + aa∗ bb) ∗ (ε + aa∗ + aa∗ b).
Donner un automate non déterministe reconnaissant L. Déterminer l’automate minimal A reconnaissant L.
Donner un automate non déterministe avec ε -transitions reconnaissant M. Déterminer l’automate minimal B reconnaissant M.
En comparant les deux automates obtenus A et B déduire que L = complémentaire(M). En termes d’automate, le complémentaire d’un automate A revient à rendre les états entrants en états terminaux et vice-versa.
Après avoir déterminer le langage ou grammaire de L, on forme l’automate pour la méthode de Glushkov :
Puis on le déterminise :
On renomme les états dans l’ordre par A, B, C, D, E, F pour éviter les ambiguïtés. Puis on minimise :
De même pour l’automate reconnaissant M :
On le déterminisme (on remarquera que l’on forme un état poubelle) :
On renomme les états dans l’ordre par K, L, M, N pour éviter les ambigüités. L’automate est déjà minimal.
On constate que la seule différence entre les automates déterministes A et B est que les états finals de l’un sont non-finals dans l’autre. D’où on peut déduire que leurs langages sont complémentaires.
