Vous trouverez sur cette page des exercices corrigés sur l’optimisation des automates, la déterminisation et la minimisation.

Déterminisation

Exercice 1

Déterminiser les automates suivants :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation.

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

Après déterminisation nous obtenons l’automate suivant :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

Exercice 3

Soit L le langage accepté par l’automate A ci-dessous :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 !

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

On déterminise l’automate :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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:

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 à :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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é):

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

Sa déterminisation conduit à l’automate suivant :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

Aucune feuille ne correspond à un état final, notons que toutes les feuilles finissent dans le puits.

L’automate déterministe :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

Les états {1} et {1,3} ont les mêmes règles. On trouve donc l’automate minimal :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

2 – Expression Rationnelle (ab + b(a + b))∗ . On commence par construire un automate par la méthode de Glushkov :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

De même l’automate est déjà déterministe. Après minimisation nous avons l’automate suivant :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

3 – Pour minimiser A3, on doit d’abord le déterminiser. Voici le résultat de l’algorithme de déterminisation :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

Et après minimisation :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

4 –  L’automate est déjà déterministe, après minimisation nous obtenons :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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 :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

Puis on le déterminise :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

On renomme les états dans l’ordre par A, B, C, D, E, F pour éviter les ambiguïtés. Puis on minimise :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

De même pour l’automate reconnaissant M :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

On le déterminisme (on remarquera que l’on forme un état poubelle) :

exercices corrigés sur l'optimisation des automates, la déterminisation et la minimisation

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.

Partager
fr_FRFR
%d blogueurs aiment cette page :