Cours n° 6, 22 novembre 2011

Jean-François Perrot

Tout langage reconnaissable par un automate fini est régulier
Théorème de Kleene

1. Construction d'un automate reconnaissant le langage donné par une e.r.
   1. Premier exemple
   2. Second exemple, où apparaît l'opérateur d'union
      
      
2. Réciproquement, construire une e.r. pour le langage reconnu par un automate fini
   1. L'algorithme de McNaughton & Yamada

Construction d'un automate reconnaissant le langage donné par une e.r.

• Premier exemple

  Ce procédé donne donne pour l'expression xy*xx*y :
  
  
  
  
  
  Pouvons-nous interpréter ce croquis ? Complètement !
  
  1. La transition 0 -> 1 par la lettre x correspond à l'automate minimal reconnaissant le singleton {x}, avec 1 terminal.
     
     
     
     
     
  2. La transition 3 -> 4 par la lettre y correspond à l'automate minimal reconnaissant le singleton {y}, avec 4 terminal.
     
     
  3. Le sous-automate formé par les états 2, 3, 4 est donc exactement ce que nous aurions construit pour reconnaître y*,
     à ceci près que la construction de Thompson ajoute un état terminal unique atteint par des ε-transitions à partir de "nos" états terminaux.
     
     
     
     
     
  4. L'ε-transition 1 -> 2 est donc bien celle qui est prévue pour reconnaître le produit xy*.
     
     
     
     
     
  5. De même, le sous-automate formé par les états 6 à 10 est exactement ce que nous aurions construit pour reconnaître  xx*.
     
     
     
     
     
  6. Et la transition 12 -> 13 par la lettre y correspond à l'automate minimal reconnaissant le singleton {y}.
     et le sous-automate de 8 à 13 reconnaît donc xx*y.
     
     
     
     
     
  Nous voyons donc que l'algorithme de Thompson n'est pas très différent de l'application systématique des procédés vus au cours 5 
  - du moins, en l'absence de l'opération d'union, car là il suit vraiment une autre voie.
  
  

• Second exemple, où apparaît l'opérateur d'union

  Nous reprenons notre exemple scolaire : en notation acceptable par le logiciel automate : (aa|b)*ab(bb)*
  
  
  
  C'est dans la partie 0-9 que se situe la nouveauté.
  
  
  1. À partir de {aa}:   et de {b} :
     le logiciel construit {aa}∪{b} :
     qui n'est pas du tout ce que prévoit le cours 5 !
     
     
  2. Pas de produit direct des ensembles d'états, mais
     
     • leur réunion, 
     • deux transitions spontanées d'un nouvel état initial vers les deux étatis initiaux,
     • un unique état terminal atteint par deux transitions spontanées depuis les états terminaux.
     Bref un automate non-déterministe... et pourquoi pas ?
     Dans la mesure ou toute la construction se fait avec du non-déterminisme, sans chercher à déterminiser et à réduire à chaque pas,
     ce procédé se justifie !
     
     
  3. La suite de la construction suit les mêmes lignes que notre premier exemple.

Réciproquement, construire une e.r. pour le langage reconnu par un automate fini

L'algorithme de McNaughton & Yamada

1. L'étape 0 correspond aux calculs qui ne passent par aucun état intermédiaire : c'est-à dire aux transitions elles-mêmes.
   
   
   
   
   
2. L'étape 1 correspond aux calculs qui ne passent que par l'état 0. 
   Par rapport à l'étape 0, on voit seulement apparaître l'aller-retour 1-0-1 provoqué par le mot bb.
   
   
   
   
   
3. L'étape 2 correspond aux calculs qui ne passent que par les états 0 et 1.
   On voit fleurir les (bb)* : on peut en effet tourner indéfiniment autour de 1.
   À noter que le mot vide n'est pas pris en compte, d'où (bb)+ et non (bb)* pour 1-1.
   
   
   
   
   
4. L'étape 3 correspond aux calculs qui ne passent que par les états 0, 1 et 2.
   On voit apparaître la boucle sur 2 par b, qui est aussitôt distribuée.
   
   En effet, d'une manière générale, on calcule l'e.r. de l'étape 3 en fonction des e.r. de l'étape 2 comme suit :
   Soit E_s,s' l'e.r. décrivant les chemins de s à s' à l'étape 2, et F_s,s' l'e.r. décrivant les chemins de s à s' à l'étape 3.
   F_s,s' = E_s,s' ∪ E_s,2 (E_2,2)*E_2,s' , puisque pour aller de s à s' en ne passant que par 0, 1 et 2,
   
   • soit on ne passe pas par 2, donc le chemin est dans E_s,s' 
   • soit on passe par 2, donc
     
     1. on y va une première fois par un chemin qui est dans E_s,2 , 
     2. on décrit un circuit autour de 2 qui est dans E_2,2, circuit que lon répère jusqu'à ce que ...
     3. on quitte 2 une dernière fois par un chemin qui est dans E_2,s' .
   Ce raisonnement est général et vaut pour toutes les étapes.
   
   
   
   
   
5. L'étape 4 correspond aux calculs de s à s' qui ne passent que par les états 0, 1, 2 et 3, c'est-à-dire à tous les calculs.
   Et par conséquent l'e.r. cherchée peut être affichée.
   
   
   
   
   
   Comme certaines expressions sont trop longues pour s'écrire dans leurs cases - le logiciel offre une visualisation améliorée
   obtenue en cliquant dans la case que l'on veut examiner :
   
   
   
   
   
   
6. Et à la fin du calcul, le résultat officiel !
   
   
   
   
   Est-il évident que notre estimation précédente [fondée sur le renversement de (aa|b)*ab(bb)*]
   et ce résultat donné par la machine ont bien la même valeur ?
   C'est-à-dire, que (bb)*ba(aa|b)*  =  b(bb)*ab*|b(bb)*ab*a(ab*a)*ab* ?
   
   On a (bb)*ba  =  b(bb)*a, reste donc à démontrer que b(bb)*a(aa|b)* =  b(bb)*ab*|b(bb)*ab*a(ab*a)*ab*
   c'est-à-dire que (aa|b)* = b*|b*a(ab*a)*ab* :
   
   
   • l'inclusion de droite dans gauche est facile : à droite les a vont toujours par 2 ;
     
   • l'inclusion de gauche dans droite est moins évidente :
     tout mot w de (aa|b)* qui contient au moins un a en contient au moins 2,
     il peut donc se factoriser en marquant le premier et le dernier a, soit w = b^pafab^q ; 
     comme le premier a est suivi d'un a, et que le dernier a est précédé d'un a, le facteur médian f, s'il n'est pas vide,
     doit être de la forme aga ; si f est vide, ou si g ne contient point de a, le mot w est bien dans le membre droit.
     Si g contient des a, ceux-ci vont par 2, et en marquant la première occurrence g se factorise en g = b^raah.
     Si h ne contient point de a, f est de la forme aga = ab^raab^sa et le mot w est bien dans le membre droit.
     Si h contient des a, le même raisonnement s'applique : on peut donc procéder par récurrence sur la longueur de w.
     
   
   Doutez-vous à présent de l'intelligence des machines ?