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

Interrogation écrite du 01/12/2011

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.)
   
   
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 !
   
   
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.
   
   
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 ?
     
     
   • 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.
     
     
   • 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.