Langages réguliers et hors-contexte

Cours M1 INaLCO, 2009-2010

Interrogation écrite du 03/12/09 : Corrigé

1. On considère un alphabet à quatre lettres X = {a, b, d, s}, et les trois expressions régulières
   
   • E = ab+s ∪ ad ∪ abb+d
   • F = (s ∪ d) (a ∪ bb+a) 
   • G =  E ∪ F 
     
     
   Construire les automates déterministes minimaux reconnaissant les trois langages
   décrits par E, F et G respectivement.
   
   
   • Pour E, qui est la réunion de trois langages,
     on construit un automate à trois états terminaux correspondant chacun à un des trois langages,
     en jouant sur l'égalité bb+ = bbb* = bb*b.
     
     
     
     Mais cet automate est non-déterministe, avec 2 transitions par b depuis l'état 3.
     On le rend déterministe en dédoublant l'état terminal 4 et en reportant la boucle sur l'état 5.
     
     
     
     Mais cet automate n'est pas minimal, car les 4 états terminaux ont le même avenir (expression reprise à Alain Courrier)
     à savoir l'ensemble réduit au mot vide, ils sont donc équivalents.
     La réduction ne va pas plus loin, comme on le voit immédiatement. L'automate minimal est :
     
     
     
     
   • Pour F, qui est le produit de deux langages,
     on construit "en série" un automate déterministe :
     
     Comme précédemment, et pour la même raison, les deux états terminaux sont équivalents,
     et la réduction donne comme automate minimal :
     
     
   • Pour G, réunion des deux précédents langages, à partir des deux automates minimaux déjà obtenus
     on construit "en parallèle" un automate qui, en l'occurrence, reste déterministe :
     
     Encore une fois, les deux états terminaux sont équivalents et la réduction s'arrête là.
     Voici l'automate minimal :
     
   
   
2. Voici un superbe automate fini !
   
   
   Est-il déterministe ? Est-il minimal ?
   Le cas échéant, le rendre détermniste et le réduire.
   À partir de sa version réduite, donner une expression régulière pour le langage qu'il reconnaît.
   
   Il suffit de l'inspecter pour voir que l'automate est déterministe, chaque état ayant au plus une transition pour chaque lettre
   (les transitions absentes étant réputées envoyer sur l'état-poubelle, non représenté), et sans aucune ε-transition.
   Mais il n'est pas minimal ! Les trois états 2, 3 et 5 sont équivalents, car chaque transition les envoie tous les 3 sur le même :
   
   •  n -> 4
   •  a -> 5
   •  s -> 3
   Ils ont donc tous les trois le même avenir - et la réduction ne va pas plus loin.
   L'automate minimal est donc :
   
   et l'expression régulière associée la plus simple s'écrit ss(a|s)*n.
   
   
3. Voici une redoutable expression régulière : xy(z|x)*y(y|z(z|x)*y)*x
   
   Construire méthodiquement un automate déterministe qui reconnaît le langage qu'elle décrit,
   puis le réduire si nécessaire.
   
   En fait, cette expression n'est pas redoutable du tout !
   En progressant de gauche à droite, tout s'arrange à merveille pour conserver le déterminisme...
   
   
   et le résultat est clairement minimal !