Langages réguliers et hors-contexte

Cours M1 INaLCO, 2009-2010

Interrogation écrite du 05/11/09

1. On considère l'alphabet X = {0, x, 7, 9, h}, et l'expression régulière suivante sur cet alphabet,
   écrite en syntaxe standard du logiciel automate :
   
   E = (7|9)+|0(7+|x(7|9|h)+)
   
   
   1. Transcrire cette expression en notation mathématique (avec "∪" pour la réunion et "." pour le produit).
      
      
   2. Les deux sous-ensembles (7|9)+ et 0(7+|x(7|9|h)+) sont-ils disjoints ?
      
      
   3. Les mots suivants appartiennent-ils au langage de l'expression, et pourquoi ?
779, 0779, 779h, 0779h, 0x779h, h779, 0h779, 0xh779
      
   
   
   
2. 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 
     
   1. Les mots suivants appartiennent-ils à l'un des trois langages décrits par nos trois expressions (et pourquoi) ? abbs, abbd, ba, abbsba, abbdba
      
      
   2. Les trois langages décrits par nos trois expressions sont-ils deux à deux disjoints  (et pourquoi) ?
      
      
   
   
3. On considère un alphabet à cinq lettres X = {f, g, d, x, v}, et l'expression régulière sur X
   E = fgd ∪ fg(xv)*xd 


   1. Les mots suivants appartiennent-ils au langage L décrit par notre expression (et pourquoi) ?
fd, fgd,  fgxd, fgxvxvd, fgxvxvxd
      
      
   2. Interprétation :
      on lit les mots de L comme des expressions mathématiques où une fonction est appliquée à ses arguments.
      
      
      • la lettre f est le nom de la fonction
      • la lettre x désigne de manière générique un argument quelconque
        
      • la lettre g représente la parenthèse ouvrante
      • la lettre d représente la parenthèse fermante
      • la lettre v représente la virgule
      
      Exemples : les trois mots de la question 1 se lisent respectivement
      "f)", "f()", "f(x)", "f(x,x,)" et "f(x,x,x)".
      
      Donner une description générale en français des mots du langage L ainsi interprétés.