Cours n° 3, 20 octobre 2011

Jean-François Perrot

Réflexions diverses sur les expressions régulières

1. I. À quoi servent les e.r. ?
   1. Un problème général en informatique : définir en termes finis un ensemble infini.
   2. Dans le cas particulier des langages (ensembles de mots)
   3. Dans le cas très particulier des langages réguliers
      
      
2. II. Comment fonctionnent les e.r. ?
   1. Calcul des langages, valeur
   2. Lois du calcul sur les langages
   3. Plusieurs expressions équivalentes pour la même valeur
   4. Exemples
      
      
3. III. La classe des langages réguliers et ses propriétés de fermeture
   1. Par définition,
   2. Hypothèse
   3. Langages et expressions, questions de syntaxe
   4. Exemple pour l' intersection
   5. Exemple illustrant les lois de De Morgan
      
      
4. IV. Prochains épisodes

I. À quoi servent les e.r. ?

1. Un problème général en informatique : définir en termes finis un ensemble infini.

   • Quand ils veulent donner en extension un ensemble infini, les mathématiciens ont l'habitude d'écrire, de manière informelle,
     des points de suspension : { Pierre, Paul, Jacques, Jules, Michel, Nestor, ... } ou {0, 2, 4, 6, 8, ...}.
     Le lecteur est censé percevoir intuitivement la relation de récurrence entre les premiers termes et ainsi prolonger la suite ad libitum - ce qui représente en fait un retour à la définition de l'ensemble en compréhension.
     Savoir le faire est souvent considéré comme un test de compétence mathématique, voire d'intelligence humaine.
     C'est un problème classique pour l'intellignce artificielle (connu sous le nom de "compléter une suite").
     
     
   • Pour les informaticiens, cette notation bien commode n'est pas de mise, car les machines ne la comprennent pas !
     Il leur faut une définition explicite et exhaustive, et cette définition doit être formulée par un objet fini
     (texte, formule logique, programme, etc).
     Ainsi, un programme (qui est un texte fini) peut être vu comme la définition de l'ensemble infini des séquences de calculs
     auxquelles son exécution pourra donner naissance.
     
     
   • Il faut bien voir que l'exigence d'une définition en termes finis impose une sévère contrainte de régularité à l'ensemble défini. Le tout est de mettre en relation les moyens employés pour la défnition et la nature de ces régularités.
   
   

2. Dans le cas particulier des langages (ensembles de mots)

   on emploie pour les définir deux classes de procédés, les grammaires et les automates.
   
   
   • Les grammaires permettent de construire les mots du langage.
     Le terme grammaire est pris par les informaticiens en un sens voisin de son sens ordinaire (la grammaire française....),
     plus précisément au sens de la grammaire générative des linguistes.
     Il désigne un ensemble (fini) de règles de construction qui assurent que tout mot produit en les utilisant fait partie du langage.
     Et réciproquement, que tout mot du langage peut être effectivement construit en employant ces règles.
     Elles reviendront plus tard dans ce cours.
     
     
   • Les automates permettent de décider si un mot donné appartient ou non au langage.
     C'est le point de vue opposé à celui de la grammaire.
     Le cas des automates finis va particulièrement nous occuper ici.
     
     
   • La théorie des langages, branche de l'informatique théorique, établit une correspondance entre classes de langages, classes de grammaires et classes d'automates.
     Nous nous occupons ici de la classe des langages réguliers, à laquelle répond la classe des grammaires linéaires unilatères (voir au 2nd semestre) et la classe des automates finis.
     Nous aborderons au second semestre la classe des grammaires dites hors-contexte (en anglais context-free),
     associée à la classe des automates à pile (push-down automata) et à la classe des langages également appelés hors-contexte.
   
   

3. Dans le cas très particulier des langages réguliers

   intervient un troisième procédé de définition : les expressions régulières, dont il est question ici.
   Cette classe de langages très remarquable peut aussi faire appel à un quatrième formalisme bien différent,
   celui de la logique monadique du second ordre (Théorème de Büchi), dont nous ne dirons rien
   [pour vous en faire une idée, voyez ici].

II. Comment fonctionnent les e.r. ?

1. Calcul des langages, valeur

   Comme il a été dit précédemment, une e.r. représente un calcul sur les langages,
   et ce calcul aboutit à un langage qui est la valeur de l'expression.
   C'est cette valeur qui est visée quand on écrit une égalité comme "yx*xy*x  = yxxx* ∪ yxyy*x ∪ yxxx*yy*x" :
   les deux expressions elles-mêmes sont bien différentes !
   La situation est tout-à-fait semblable à celle des expressions algébriques et de leurs valeurs numériques,
   avec toutefois une différence de taille :
   
   
   • Nous sommes capables de désigner la valeur numérique d'une expression algébrique,
     car nous savons désigner les nombres : 2+2 = 4...
     Et nous voyons bien que cette valeur existe en elle-même, indépendamment de l'expression
     qui n'est qu'une des nombreuses manières de l'obtenir.
     
     
   • Mais dès qu'une e.r. a pour valeur un langage infini (dès qu'elle contient une étoile),
     nous n'avons (pour l'instant) aucun moyen pour désigner "directement" ce langage...
     Pourtant, lui aussi existe en lui-même, indépendamment de l'expression
     qui n'est qu'une des nombreuses manières de l'obtenir.
     
     
   Cette observation fait naître le besoin d'une désignation intrinsèque pour un langage,
   d'un moyen qui, une fois fixé, donnerait une désignation unique pour un langage donné.
   Les e.r. ne satisfont pas du tout ce besoin, comme nous allons le voir en détail !
   La solution viendra avec les automates finis, au prochain cours.
   

2. Lois du calcul sur les langages

   L'essentiel du cours 2 a été consacré aux propriétés des opérations sur les langages
   (commutativité ou non, associativité, distributivité).
   Ajoutons-en deux autres relatives à l'opération étoile
   [ rappelons que dans la notation usuelle le symbole unaire "*" a la plus forte priorité,
   c'est-à dire que  AB* = A(B*) et non pas (AB)* ] :
   

   Pour tout langage L, on a LL* = L*L.
   Cette valeur commune est souvent notée L+ .
   

   En effet, un mot de L+ est la concaténation d'une suite finie non-vide de mots de L,
   soit u1u2u3...uk, avec k > 0 et ui∈L pout tout i.
   que l'on peut écrire sans parenthèses en raison de l'associativité de la concaténation.
   On peut aussi mettre en évidence le premier facteur : u1(u2u3...uk) ou le dernier (u1u2u3...)uk :
   dans un cas on manifeste que le mot est dans LL*, dans l'autre, qu'il est dans L*L.
   

   Pour tous langages A et B, on a (A∪B)* = (A*B)*A* = A*(BA*)*

   Tout mot de (A∪B)* la concaténation d'une suite finie non-vide de mots pris dans A ou dans B,
   soit u1u2u3...uk, avec k > 0 et ui∈A∪B pout tout i.
   On peut lire cette suite en "marquant" les facteurs qui sont dans B, séparés par des suites de facteurs
   (éventuellement vides) pris dans A, donc comme une suite alternée de facteurs tantôt dans A*, tantôt dans B.
   Ces suites alternées sont décrites aussi bien par l'expression (A*B)*A* que par A*(BA*)*,
   par un raisonnement analogue au précédent.
   
   

3. Plusieurs expressions équivalentes pour la même valeur

   Toutes ces lois ont pour conséquence que des expressions ayant la même valeur peuvent prendre des formes très différentes !
   Ce qui ruine tout espoir de désignation unique des langages avec les e.r.
   Nous allons en voir quelques exemples.
   
   Notations :
   
   • Nous désignons par X l'alphabet de base, supposé contenir au moins deux lettres : X = {x, y, z,…}.
     X* désigne alors l'ensemble des mots écrits avec X.
     Nos langages sont donc les sous-ensembles de X*.
     
     
   • Nous ferons souvent l'abus de notation consistant à identifier un mot avec le singleton formé par ce mot :
     nous écrirons "x" au lieu de "{x}" et "xyz" au lieu de "{xyz}" ou de "{x}{y}{z}".
     Nous considérons que "X" est une e.r., abréviation de "{x}∪{y}∪{z}...",
     et par conséquent que "X*" est une e.r.
     
     
   • Pour indiquer le complément d'un sous-ensemble de X ou de X*, plutôt que le symbole unaire ∁
     nous emploierons la controblique "\" binaire :
     Pour A ⊆ X*, "X*\A" désigne le complémentaire de A dans X*,
     et pour une lettre  x∈X, "X\x" désigne l'ensemble des autres lettres de l'alphabet.
     De même, nous considérons que "X\x" est une e.r., abréviation de "{y}∪{z}...".

4. Exemples

   • Soit L₁  = { w ∈ X*| w contient au moins une occurrence de y }
     On peut le décrire par l'e.r. "X*{y}X*", en notation courante "X*yX*".
     Mais aussi, en mettant en évidence la première occurrence de y, par l'e.r. "(X\y)*yX*"
     et aussi bien, en mettant en évidence la dernière occurrence de y, par "X*y(X\y)*".
     
     
   • Le complémentaire de L₁, X*\L₁ est décrit pa l'e.r. "(X\y)*".
     
     
   • Soit de même L₂  = { w ∈ X*| w contient au moins une occurrence de x } = X*xX*.
     L'intersection L₁ ∩L₂ = { w ∈ X*| w contient au moins une occurrence de x et une occurrence de y}
     se définit en deux parties, selon que l'occurrence de x précède ou suit celle de y :
     "X*xX*yX*" pour l'une, "X*yX*xX*" pour l'autre, donc au total
     L₁ ∩L₂ = "X*xX*yX* ∪ X*yX*xX*".
     
     
   • Rappelons l'exemple détaillé au cours 2 où nous avons démontré que les deux e.r.
     "yx*xy*x" et "yxxx* ∪ yxyy*x ∪ yxxx*yy*x" avaient la même valeur.
     

III. La classe des langages réguliers et ses propriétés de fermeture

1. Par définition,

   la classe des langages réguliers est formée des langages qui peuvent être décrits par une e.r.
   
   Sachant ce que sont les e.r., cette définition est équivalente à la suivante :
   
   la classe des langages réguliers est la plus petite classe de langages qui
   
   • contient tous les singletons de lettres
   • est fermée par les trois opérations d'union, de concaténation (ou produit) et d'étoile.
   
   L'expression "est fermée par" signifie que si L₁ et L₂ sont des langages réguliers,
   alors leur union L₁ ∪ L₂, leur concaténation L₁ L₂, et leurs itérés (étoile) L₁* et L₂* 
   sont aussi des langages réguliers.
   
   Cette observation met en lumière le rôle des propriétés de fermeture de cette classe de langages
   par rapport aux opérations sur les langages, et elle conduit à se poser la question :
   qu'en est-il des autres opérations, comme l'intersection, le passage au complémentaire, etc ?
   
   

2. Hypothèse

   Les quelques exemples ci-dessus pourraient être multipliés, et soutenir l'hypothèse que
   la classe des langage réguliers est aussi fermée par l'intersection et le passage au complémentaire.
   Notons au passage que, en vertu des lois de De Morgan, la fermeture par complémentation implique
   la fermeture par intersection (puisque la classe est fermée par union).
   Reste à démontrer cette hypothèse...
   Nous le ferons grâce aux automates finis.
   En atendant, voici des exemples d'utilisation de la syntaxe étendue du logiciel automate, qui permet justement
   de lui donner des expressions mettant en œuvre ces deux opérations supplémentaires.
   
   

3. Langages et expressions, questions de syntaxe

   Soulignons la différence essentielle entre expression régulière et langage régulier :
   
   • le langage est la valeur de l'expression (on dira aussi que l'expression décrit le langage) ;
   • plusieurs expressions différentes peuvent avoir le même langage pour valeur ;
   • les opérations que nous avons vues portent sur les langages ;
   • les expressions ont une syntaxe (dont il sera parlé longuement au second semestre)
     qui fait intervenir différents symboles qui représentent les opérations.
     
     
   L'intervention de deux classes d'opérations met en lumière cette différence :
   
   
   • d'un côté les trois opérations d'union, de produit et d'étoile, qui entrent dans la définition des langages réguliers,
     et qui figurent dans la syntaxe "stricte" des expressions régulières (la syntaxe standard du logiciel automate)
     
   • de l'autre l'intersection et le passage au complémentaire, qui sont a priori étrangères à la régularité des langages,
     si bien que l'on doit se demander :
     étant donné deux langages réguliers A et B, leur intersection A∩ B est-elle aussi un langage régulier ?
     le complémentaire de A, ∁A (ou ∁B, celui de B) est-il encore un langage régulier ?
     
     
   Le fait que la réponse à ces deux questions soit positive (comme nous le verrons plus tard) conduit à introduire ces opérations
   dans une syntaxe étendue pour les expressions régulières, qui permet de définir des langages régulierrs
   avec des moyens linguistiques plus puissants. 
   Pour le logiciel automate, cette syntaxe étendue utilise
   
   • l'esperluette "&" pour désigner l'intersection (avec une priorité plus forte que celle de la réunion "|")
   • et le point d'exclamation en position postfixée pour noter le passage au complémentaire
     (avec une priorité plus forte que tous les autres).
     
     
   Cette syntaxe étendue n'est utilisable que pour la donnée d'une e.r., le logiciel emploie toujours la syntaxe stricte
   pour afficher l'e.r. qu'il calcule à partir d'un automate minimal.
   On peut donc l'employer pour traduire en syntaxe stricte une e.r. donnée en syntaxe étendue.

4. Exemple pour l' intersection

   1. Soit A le langage formé des mots sur l'alphabet {a, b}
      
      • commençant par b
      • se terminant par a
      • et contenant un nombre pair de a 
        
      On peut le représenter par l'expression régulière bb*(ab*ab*)*ab*a
      
      qui se verbalise ainsi :
      
      • Tout mot répondant aux trois conditions précédentes se décompose d'une manière unique en marquant les occurrences de a.
        
      • Deux occurrences consécutives de a sont séparées par un nombre quelconque de b, éventuellement nul,
        donc par un mot de b*.
      • Pour avoir un nombre pair de a, tout en se terminant par a, le mot doit comporter un nombre impair de a avant le a final.
        Ce nombre impair de a peut toujours s'obtenir comme un nombre pair de a suivi d'un dernier a, c'est-à-dire sous la forme
        d'une concaténation de mots contenant exactement 2 occurrences de a, suivie d'un dernier a, à savoir (ab*ab*)*a
        
      • Avant le premier a, il n'y a que des b, et il y en a au moins 1, à savoir l'initiale, d'où un facteur gauche bb*.
      • Juste avant le dernier a (la dernière lettre du mot) il n'y a que des b, mais peut-être aucun, d'où un pénultième facteur b*.
      
      
   2. Soit B le langage formé des mots sur l'alphabet {a, b}
      
      • commençant par b
      • se terminant par a
      • et contenant un nombre pair de b 
        
      De la même manière que ci-dessus, on peut le représenter par l'expression régulière ba*b(a*ba*b)*a*a
      
      
   3. Le langage A∩ B se décrit comme l'ensemble des mots sur l'alphabet {a, b} qui
      
      • commençent par b
        
      • se terminent par a
      • contiennent un nombre pair de a 
        
      • et contiennent un nombre pair de b .
        
      Il est également représentable par une e.r., mais cette dernière est beaucoup plus compliquée !
      
      Voici celle que calcule le logiciel automate : on lui donne à lire (en syntaxe étendue : détails ici) l'expression
       bb*(ab*ab*)*ab*a & ba*b(a*ba*b)*a*a
      
      et il renvoie en syntaxe standard
      ((bb)+a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a(((bb)*a|(bb)*ba(aa|
ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a)*
      
      Cette expression est un produit de 3 facteurs, dont le dernier est une étoile :
      
      1. {(bb)+a|(bb)*ba[aa|ab(bb)*ba]*[b|ab(bb)*a]}
      2. {b[aa|ab(bb)*ba]*[b|ab(bb)*a]}*a
      3. {[(bb)*a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a)]
  [b(aa|ab(bb)*ba)*(b|ab(bb)*a)]*a}*  
         
      Les deux mots les plus courts décrits par cette expression sont bbaa et baba (pourquoi ?),
      qui sont bien les deux mots les plus courts du langage d'après sa description.
      Nous n'irons pas plus loin dans la vérification que l'expression en question a effectivement pour valeur le langage A∩ B !
      
      

5. Exemple illustrant les lois de De Morgan

   1. Par le même procédé que ci-dessus, on demande à automate de calculer une expression régulière "stricte"
      pour l'expression étendue représentant le complémentaire ∁(A∩ B), soit
      ( ((bb)+a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a(((bb)*a|(bb)*ba(aa|
ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a)* ) ! 
      [ne pas oublier les parenthèses autour de l'expression, en raison de la forte priorité de l'opérateur postfixé "!"
      qui représente le passage au complémentaire dans la syntaxe étendue d'automate ]
      
      
   2. De même, on lui demande une expression régulière "stricte"
      pour l'expression étendue représentant l'union des complémentaires ∁A∪ ∁B, soit
      ( bb*(ab*ab*)*ab*a ) ! | ( ba*b(a*ba*b)*a*a ) !
      
      
   3. Dans les deux cas, on obtient la même expression
      - alors qu'on aurait pu obtenir deux expressions différentes représentant le même langage -
      à savoir :
      
      ^|(bb)*b|(bb)*ba(aa|ab(bb)*ba)*(a|ab(bb)*b)|((bb)+a|(bb)*ba(aa|ab(bb)*ba)*(b|
ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*b(aa|ab(bb)*ba)*(a|ab(bb)*b)|((bb)+a|
(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a(((bb)*a|
(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a)*((bb)*b|
(bb)*ba(aa|ab(bb)*ba)*(a|ab(bb)*b)|((bb)*a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))
(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*b(aa|ab(bb)*ba)*(a|ab(bb)*b))|a(a|b)*|(bb)+|
(bb)*ba(aa|ab(bb)*ba)*ab(bb)*|((bb)+a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|
ab(bb)*ba)*(b|ab(bb)*a))*b(aa|ab(bb)*ba)*ab(bb)*|((bb)+a|(bb)*ba(aa|
ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a(((bb)*a|(bb)*ba(aa|
ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a)*((bb)+|(bb)*ba(aa|
ab(bb)*ba)*ab(bb)*|((bb)*a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|
ab(bb)*ba)*(b|ab(bb)*a))*b(aa|ab(bb)*ba)*ab(bb)*)|(bb)*ba(aa|ab(bb)*ba)*|((bb)+a|
(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*b(aa|
ab(bb)*ba)*|((bb)+a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|
ab(bb)*a))*a(((bb)*a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|
ab(bb)*a))*a)*((bb)*ba(aa|ab(bb)*ba)*|((bb)*a|(bb)*ba(aa|ab(bb)*ba)*(b|ab(bb)*a))
(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*b(aa|ab(bb)*ba)*)|((bb)+a|(bb)*ba(aa|
ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*|((bb)+a|(bb)*ba(aa|
ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a(((bb)*a|(bb)*ba(aa|
ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*a)*((bb)*a|(bb)*ba(aa|
ab(bb)*ba)*(b|ab(bb)*a))(b(aa|ab(bb)*ba)*(b|ab(bb)*a))*
      
      Le mot le plus court du langage est vite trouvé, c'est le mot vide qu'automate  écrit "^"...
      Nous n'irons pas plus loin !
      

IV. Prochains épisodes

1. Introduire la notion d'automate fini et de langage reconnu par un automate.
   Nous obtiendrons ainsi un moyen de désignation intrinsèque du langage reconnu (l'automate minimal).
   
   
2. Étudier les propriétés de fermeture de la classe des langages reconnaissables par des automates finis.
   Cette étude fera appel à la notion d'automate non-déterministe,
   elle aboutira au fait que tout langage régulier est reconnaissable par un automate fini.
   Ceci nous fournira un moyen simple pour démontrer que certains langages ne sont pas réguliers.
   
   
3. Étant donné une e.r., construire un automate fini qui reconnaît son langage-valeur.
   Ceci établira que, réciproquement, tout langage reconnaissable par un automate fini est régulier.
   On aura ainsi démontré le théorème de Kleene.
   dont un corollaire et la fermeture par complémentation évoquée plus haut.
   
   
4. Passer à la pratique des e.r....