Langages réguliers et hors-contexte
Cours M1 INaLCO, 20011-2012

Interrogation écrite du 01/12/2011 : Corrigé

Les expressions régulières vues en cours sont en général données dans la syntaxe ordinaire (celle que lit et écrit le logiciel automate). Cette syntaxe repose sur des règles de priorité des opérateurs analogues à celles qui sont en usage dans les expressions arithmétiques. La notation complètement parenthésée n'utilise pas ces règles, elle met une paire de parenthèses autour de l'application de chaque opérateur à ses opérandes (même pour un opérateur unaire). En outre, pour plus de précision, on écrit un point pour noter la concaténation. Cette notation est plus lourde mais plus explicite. Elle représente fidèlement l'arbre associé à l'expression. Exemple l'expression (aa|b)*ab(bb)* s'écrit en notation complètement parenthésée ((((((a.a)|b)*).a).b).((b.b)*)) L'arbre associé est représenté ci-contre. On a déjà vu un exemple d'arbre au cours n° 6.

1. Réécrivez cette expression en notation complètement parenthésée, et dessinez l'arbre correspondant.
   (Il est recommandé de décomposer l'expression comme la réunion de quatre parties, et de procéder morceau par morceau.)
   
   
   Cette expression et la réunion de quatre parties, elle s'écrit E = A|B|C|D, avec
   

   • A = ab+s
   • B = ad
   • C = abb+d
   • D = (s|d)(a|bb+a)
     

   
   En notation complètement parenthésée, cette quadruple réunion s'écrit E = (((A|B)|C)|D) [de même que a-b-c s'écrit ((a-b)-c) ].
   
   Réécrivons à présent ls 4 composantes, en notant explicitement l'opération de produit :
   

   • A = ((a.(b+)).s)
   • B = (a.d)
   • C = (((a.b).(b+)).d)
   • D = ((s|d).(a|((b.(b+)).a)))
     

   
   et reportons dans la réunion : E = (((((a.(b+)).s)|(a.d))|(((a.b).(b+)).d))|((s|d).(a|((b.(b+)).a))))
   
   Les quatre arbres sont ainsi dessinés :
   
   

   A

   B

   C

   D

   et l'arbre tout entier prend la forme :
   E
   
   
2. Dans le langage L décrit par cette expression, y a-t-il un mot qui commence par b ? un mot qui se termine par b ?
   un mot contenant deux occurrences d'une lettre autre que b ?
   Ne vous contentez pas de répondre par oui ou par non, motivez votre réponse !
   
   
   En inspectant les quatre composantes A, B, C et D, on constate que
   

   • tous les mots commencent par a (A, B, C ), par s ou par d (D), à l'exclusion de b ;
     
   • tous les mots se terminent par s (A), par d (B, C) ou par a (D), ici aussi à l'exclusion de b ;
   • les seuls facteurs répétant une même lettre deux fois se trouvent
     
     • dans A (b+)
     • dans C (b.b+)
     • dans D (b.b+)
     ils ne concernent que la lettre b.
     
   
   
3. Interprétation de l'alphabet X,
   
   • la lettre b représente le caractère espace, alias blanc (ASCII 0x20)
   • la lettre s représente une ponctuation simple (le point et la virgule)
   • la lettre d représente une ponctuation double (le point-virgule, les deux-points, le point d'interrogation et le point d'exclamation)
     
   • la lettre a représente autre chose (une lettre ou un chiffre).
     
     
   L'expression E est censée représenter les mots minimaux où apparaissent des manquements aux règles typographiques françaises,
   ainsi formulées par Wikisource :
   
   
   1. Les signes de ponctuation simple (. ,) se collent au mot qui les précèdent, et sont suivis d’un espace (un seul).
   2. Les signes de ponctuation double (; : ! ?) doivent être précédés et suivis d’un espace (un seul).
      
   
   Justifiez - ou infirmez - cette affirmation.
   
   
   • Arguments pour :
     
     1. 
        
4. On considère l'automate fini A que voici (où 0 est l'état initial, et 4 l'unique état terminal) :
   
   
   N.B. Suivant les conventions du logiciel automate, l'état "poubelle" n'est pas dessiné.
   
   
   • Est-il déterministe ?
     
     
     Oui assurément !
     Il n'y a pas d'ε-transitions, et en chaque état chaque lettre de l'alphabet opère au plus une transition
     - l'absence de transition étant interprétée comme un saut dans la poubelle.
     
     Il est aussi minimal - c'est une autre question, mais elle mérite qu'on la traite.
     En effet chaque état a un "avenir" différent, on peut le vérifier comme suit :
     

     0. est le seul état envoyé sur l'état terminal 4 par le mot ad, et par lui seul ;
        
     1. est le seul état envoyé sur l'état terminal 4 par les mots du langage a|bbb*a
        - qui inclut les mots a et bba, mais exclut le mot ba ;
        
     2. est le seul état envoyé sur l'état terminal 4 par le mot d, et pas par le mot s ;
     3. est le seul état envoyé sur l'état terminal 4 par les mots du langage bb*a
        - qui exclut le mot a ;
     4. est le seul état envoyé sur l'état terminal 4 par le mot vide, et par lui seul ;
     5. est le seul état envoyé sur l'état terminal 4 par le mot s, et pas par le mot d ;
     6. est le seul état envoyé sur l'état terminal 4 par les mots du langage b*a
        - qui contient les mot a, ba, et bba ;
     7. est le seul état envoyé sur l'état terminal 4 par le mot d et par le mot s.
        
        
     
     
   • En traitant séparément les quatre parties de l'expression, vérifiez que tous les mots du langage L
     sont effectivement acceptés par l'automate  A .
     
     
     Appelons L(A) le langage formé des mots acceptés par l'automate A.
     Pour prouver l'égalité d'ensembles L = L(A), nos devons comme d'habitude établir les deux inclusions L ⊆ L(A) et L(A) ⊆ L.
     L'énoncé nous invite à commencer par la première.
     
     Comme L est la réunion des quatre langages L_A, L_B, L_C, et L_D décrits par les quatre expressions composantes,
     il suffit de prouver que chacun de ces langages est inclus dans L(A).
     On y parviendra en décrivant, pour chacun d'eux, l'itinéraire que suivent les mots qui le composent au cours de leur acceptation par A.
     

     • Pour A = ab+s, cet itinéraire est 0-2-5-4 ou 0-2-5-7...7-4, selon que le mot contient une seule occurrence de b ou davantage.
     • Pour B = ad, cet itinéraire est 0-2-4.
     • Pour C = abb+d, cet itinéraire est  0-2-5-7...7-4.
     • Pour D = (s|d)(a|bb+a), cet itinéraire est  0-1-4 ou 0-1-3-6...6-4.
     
     
   • Réciproquement, en analysant séparément les blocs (2, 5, 7) et (1, 3, 6), montrez que tout mot accepté par  A
     est décrit par une des quatre parties de l'expression E, et donc appartient à L.
     
     
     On passe à la seconde inclusion L(A) ⊆ L.
     Il s'agit de montrer que chaque mot accepté par A est décrit par l'expression E, donc par une de ses quatre composantes.
     On observe qu'il y a dans A deux classes d'itinéraires partant de 0 et arrivant à 4, l'unique état terminal :
     

     1. ceux qui passent par le "carré" 2-5-7-4 ;
     2. ceux qui empruntent la voie 1-3-6.

     
     Dans la première classe, on distingue 3 parcours :
     

     1. le parcours 0-2-4, qui accepte le mot ad, décrit par l'expression B ;
     2. le parcours 0-2-5-4, qui accepte le mot abs, décrit par l'expression A ;
        
     3. les parcours de la forme 0-2-5-7...7-4, qui acceptent les mots de la forme abbb*s, décrits par l'expression A,
        et les mots de la forme abbb*d, décrits par l'expression C.
        
        

     Dans la seconde classe, on distingue 2 parcours :
     

     1. le parcours 0-1-4, qui accepte les mots de la forme (s|d)a, décrits par l'expression D ;
     2. le parcours 0-1-3-6...6-4, qui accepte les mots de la forme (s|d)bbb*a, décrits par l'expression D.

     
     Ayant ainsi épuisé les possibilités d'acceptation d'un mot par l'automate A, nous avons démontré la seconde inclusion.
     L'égalité L = L(A) est donc établie.