Compilation : 3. Automates, déterminisation et minimisation

AFD et AFN

Un AFD est un quintuplet (Q, Σ, δ, q0, F). Q est fini, q0 est initial et F est l’ensemble des états finaux. Un AFD complet possède exactement une transition par état et symbole : δ : Q × Σ → Q. Un AFN possède des ensembles de destinations et peut autoriser ε, qui ne consomme aucun caractère. Il accepte un mot si au moins un chemin complet finit dans F.

Exemple : les mots binaires se terminant par 01. q0 signifie « aucun suffixe utile », q1 « le mot courant se termine par 0 », q2 « il se termine par 01 ». L’état initial est q0.

Sur 1001, le parcours est q0 → q0 → q1 → q1 → q2 : accepté. Sur 010, le parcours finit en q1 : refusé.

Déterminiser par ensembles d’états

La ε-fermeture d’un ensemble contient tous les états accessibles par zéro ou plusieurs transitions ε. L’état initial déterminisé est ε-fermeture({q0}). Depuis T sur a, calculer ε-fermeture(⋃ δ(q,a), q ∈ T). Un ensemble est final s’il rencontre F. Répéter jusqu’à épuisement des ensembles accessibles ; ∅ devient un état puits si l’on veut un AFD complet.

AFN : q0 --0--> q0 et q1 ; q0 --1--> q0
      q1 --1--> q2 ; q2 est final
      aucune autre transition ; initial q0

Cet AFN devine le début du suffixe 01. La déterminisation retrouve l’AFD précédent. Tous les ensembles construits sont accessibles ; les autres sous-ensembles n’ont pas besoin d’être ajoutés.

Minimiser par raffinement

Supprimer les états inaccessibles puis séparer états finaux et non finaux. À chaque tour, séparer deux états d’un même bloc si leurs transitions sur un symbole conduisent à des blocs différents. Arrêter quand la partition se stabilise ; un état du quotient représente chaque bloc.

Pour l’AFD ci-dessus : P0 = {{q2},{q0,q1}}. Sur 1, q0 mène au bloc non final, q1 au bloc final ; il faut donc les séparer. P1 = {{q2},{q0},{q1}} est stable. Les trois états sont nécessaires.

Clôtures utiles

Pour complémenter, fixer Σ, déterminiser et compléter avant d’échanger finaux et non finaux. Pour l’intersection de deux AFD, construire les couples (p,q), faire évoluer les deux composantes sur le même symbole et prendre F1 × F2 pour états finaux. Les langages réguliers sont aussi clos par union, concaténation et étoile.

Pour les préfixes de L, rendre finaux les états depuis lesquels un ancien final est accessible. Pour les suffixes, utiliser comme états initiaux tous les états accessibles de l’ancien automate (ou un nouvel initial avec des arcs ε). Pour les facteurs, combiner ces deux transformations.