Langages réguliers et hors-contexte

Cours M1 INaLCO, 2009-2010

Interrogation écrite du 03/12/09

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.
   
   


2. Voici un superbe automate fini !
   
   
   Est-il déterministe ? Est-il minimal ?
   Le cas échéant, le rendre déterministe et le réduire.
   À partir de sa version réduite, donner une expression régulière pour le langage qu'il reconnaît.
   
   
   
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.