Langages réguliers et hors-contexte

Cours M1 INaLCO, 2009-2010

Interrogation écrite du 05/11/09 : Corrigé

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).
      
      En traduisant lettre à lettre on obtient : ({7}∪{9})+∪({0}.({7}+∪{x}.({7}∪{9}∪{h})+))
      Une traduction plus intelligente évite les singletons autant que possible et donne : 
{7,9}+∪({0}.({7}+∪{x}.{7,9,h}+))
      
      
   2. Les deux sous-ensembles (7|9)+ et 0(7+|x(7|9|h)+) sont-ils disjoints ?
      
      Oui, car les mots du premier commencent par 7 ou par 9, tandis que les mots du second commencent par 0.
      
      
   3. Les mots suivants appartiennent-ils au langage de l'expression, et pourquoi ?
779, 0779, 779h, 0779h, 0x779h, h779, 0h779, 0xh779
      
      
      • Oui : 779 ne contient que des 7 et des 9, il appartient donc à (7|9)+.
      • Non : 0779 commence par 0, pour être dans le langage il devrait donc se trouver dans 0(7+|x(7|9|h)+), 
        mais alors la présence d'un 9 exigerait celle d'un x après le 0, ce qui n'est pas vérifié.
      • Non : 779h n'est pas dans (7|9)+ (à cause du h final), ni dans 0(7+|x(7|9|h)+) puisqu'il ne commence pas par 0.
      • Non : 0779h a le même défaut que 0779.
      • Oui :  0x779h est un exemplaire typique du format 0x(7|9|h)+) inclus dans 0(7+|x(7|9|h)+).
      • Non : même argument contre h779 que contre 779h. 
      • Non : même argument contre 0h779 que contre 0779h. 
      • Oui : 0xh779  est du même format que   0x779h.
   
   
   
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
      
      
      • abbs ∈ ab+s ⊆ E, donc abbs ∈  E 
        
      • abbd ∈ abb+d ⊆ E, donc abbd ∈  E 
      • ba n'apparttient à aucun des langages en jeu :
        en effet ce mot commence par b, alors que les mots de E commencent par a et ceux de F par s ou par d.
      • abbsba et abbdba non plus, car les seuls mots qui se terminent par a appartiennent à F
        et doivent donc commencer par s ou par d.
      
      
   2. Les trois langages décrits par nos trois expressions sont-ils deux à deux disjoints  (et pourquoi) ?
      
      Pour alléger le discours, nous identifions les e.r. et les langages qu'elles décrivent.
      
      • E et F sont disjoints, puisque les mots de E commencent par a et ceux de F par s ou par d.
      • Comme G contient E et F, ses intersections avec E et F sont :
        
        • G∩E = E
        • G∩F = F
        Ces intersections ne sont pas vides...
      
      
   
   
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
      
      
      • le mot le plus court du langage est fgd, donc fd n'appartient pas à L.
      • fgd figure explicitement dans le premier terme de la réunion, il appartient donc au langage.
      • fgxd est obtenu dans le second terme fg(xv)*xd en prenant le mot vide (puissance 0) dans l'étoile (xv)* ;
        c'est le second mot le plus court de L (il est précédé par fgd).
      • fgxvxvd est presque bon... mais il lui manque une dernière occurrence de x juste avant le d final.
      • fgxvxvxd est un mot "typique" de L, obtenu en prenant la puissance 2 dans l'étoile (xv)* :
        fgxvxvxd = (fg)[xvxv](xd) = (fg)[xv]2(xd)
        
      
      
   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.
      
      Il s'agit des mots de la forme "f suivi d'une seule paire de parenthèses ouvrante-fermante, à l'intérieur de laquelle on trouve
      soit rien du tout (cas d'une fonction sans argument), soit une suite non-vide de x séparés par des virgules, sans virgule après le dernier x".