Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Expressions régulières
Article mis en ligne le 11 mai 2007
dernière modification le 3 juin 2021

Cet article vient à la suite d’un autre : Automates II : non-déterminisme. Nous poursuivons ainsi, guidés par MM. Hopcroft et Ullmann [1], auxquels s’est joint Rajeev Motwani, notre tour de quelques outils formels de la linguistique de la programmation, qui n’a que peu à voir avec celle des langages humains, faut-il le préciser.

*Définitions et références

Ce nouveau chapitre introduit les expressions régulières, qui permettent, comme les automates finis abordés lors des chapitres précédents, de définir des langages. Nous montrerons qu’elles sont équivalentes aux automates à états finis non-déterministes (NFA), dont nous avons montré qu’ils étaient eux-mêmes équivalents aux automates à états finis déterministes (DFA).

Comme le dit Wikipédia : une expression régulière (« regexp », RE) est une suite de caractères typographiques qu’on appelle plus simplement « motif », « pattern » en anglais. Une expression régulière sert à décrire, à dénoter un langage, dit langage régulier ; les caractères de l’expression régulière définissent les règles de ce langage. Confronter un texte à une expression régulière permet de savoir si ce texte est conforme aux règles du langage ou non ; s’il est conforme, le texte sera dit un mot du langage.

Une expression régulière sera utilisée de façon analogue à ce que nous avons vu pour les automates finis : le texte dont il faut déterminer s’il appartient ou non au langage considéré sera soumis à l’analyseur d’expressions régulières (un logiciel, par exemple le programme grep, analyseur d’expressions régulières contenu dans tout système Unix ou Linux), qui utilisera l’expression régulière qui décrit le langage comme une table de transitions. Le texte sera dit reconnu si la lecture de ses caractères successifs permet de parcourir l’expression régulière jusqu’à la fin. Voici un schéma qui montre le processus :

Figure 1 : grep analyse un texte au moyen d’une expression régulière.

**Premier exemple

Un exemple très simple aidera à comprendre : nous cherchons à décrire le langage des numéros d’immatriculation des voitures en France (nous prendrons les numéros « à l’ancienne mode », mieux adaptés à ce qu’il faut montrer). Ces numéros sont (étaient ?) composés de trois ou quatre chiffres, suivis de trois lettres, suivis de deux ou trois chiffres. Dans un premier temps nous nous limiterons à 3 chiffres, suivis de trois lettres majuscules, suivies de deux chiffres. Nous plaçons les textes à analyser dans le fichier mes-textes ci-dessous :

L’expression régulière qui désigne « un chiffre quelconque de 0 à 9 » s’écrit : [0-9]. Celle qui désigne « une lettre majuscule de A à Z » s’écrit : [A-Z]. Notre expression régulière pourra donc s’écrire (soumise à grep) :

La commande grep ci-dessus affiche les lignes du fichier mes-textes qui contiennent un texte reconnu par l’expression régulière. Le numéro de la première ligne du fichier est reconnue. Ceux de la seconde et la troisième ne le sont pas parce qu’ils contiennent des espaces supplémentaires non prévus. Ce lui de la quatrième ligne comporte des lettres minuscules, non reconnus. Ceux de la cinquième et la sixième comportent des numéros de département à trois chiffres, qui existent mais que notre expression régulière ne sait pas encore reconnaître.

**Plus de règles

Les règles de rédaction (en d’autres termes la syntaxe) pour former des expressions régulières reposent sur des caractères dits spéciaux (c’est-à-dire dotés d’une fonction syntaxique spéciale) de substitution, de groupement et de quantification :

  • Substitution : Une barre verticale sépare deux expressions alternatives : equo|aequo désigne soit equo, soit aequo. L’alternative n’existe que dans la syntaxe des expressions régulières étendues, reconnues avec l’option -E de grep, ou avec la variante egrep.
  • Groupement : Il est possible d’utiliser des parenthèses pour définir le champ et la priorité de la détection. Ainsi, (ae|e)quo désigne le même ensemble que aequo|equo. Le groupement n’existe que dans la syntaxe des expressions régulières étendues, reconnues avec l’option -E de grep, ou avec la variante egrep.
  • Quantification : En apposant des caractères de quantification à droite d’un caractère ou d’un groupe de caractères, il est possible de déterminer leur nombre de répétitions autorisé. Les quantifieurs les plus utilisés sont :
    •  ? qui permet de déclarer que l’unité de texte auquel il s’applique doit exister en zéro ou un exemplaire dans le texte examiné ;
    • * qui permet de déclarer que l’unité de texte auquel il s’applique peut être répétée un nombre quelconque, éventuellement nul, de fois ;
    • + qui permet de déclarer que l’unité de texte auquel il s’applique doit exister en au moins un exemplaire dans le texte examiné ;
    • m déclare que l’unité de texte qui précède doit figurer exactement m fois dans le texte examiné, m, déclare qu’il doit figurer au moins m fois, m,n déclare qu’il doit figurer au moins m fois et au plus n fois, n inclus. Ce dernier type de quantificateur n’existe que dans la syntaxe des expressions régulières étendues,reconnues avec l’option -E de grep, ou avec la variante egrep.

Munis de ces nouveaux outils, nous pouvons reconnaître de nouveaux modèles de numéros d’immatriculation :

On note les apostrophes qui délimitent l’expresssion régulière, et la chaîne ’ ?’ qui représente un espace, présent zéro ou une fois.

L’intérêt premier des expressions régulières réside dans leur commodité d’emploi : elles sont une notation textuelle, alors que les automates ne peuvent être représentés que par des diagrammes ou par des structures de données complexes. De ce fait les expressions régulières peuvent être utilisées et transformées facilement par les langages de programmation, d’ailleurs elles peuvent être employées elles-mêmes comme une sorte de langage de programmation, non Turing-équivalent mais efficace pour divers problèmes tels que l’analyse de textes ou la traduction de langages de programmation (cf. l’article Programmer des grammaires avec Bigloo).

Tout utilisateur d’un système Unix ou Linux a accès à un logiciel d’expressions régulières sous l’espèce de la merveilleuse commande grep (pour Global (search for) Regular Expression and Print), et ses variantes egrep, fgrep et rgrep. En voici quelques exemples :

La commande grep de la première ligne affiche les lignes du fichier mes-textes qui commencent par un point (^\., la contre-barre annule la signification particulière du point, qui isolé désigne « n’importe quel caractère »), suivi de deux caractères minuscules quelconques ([a-z]), suivis d’un espace.

Les motifs des deux lignes suivantes comportent des alternatives, (ranum|cox) et ([a-k]|[t-z]), non supportées par grep et qui exigent egrep ou grep -E, c’est-à-dire grep avec des expressions régulières étendues : la commande de la seconde ligne affiche les lignes du fichier securite.bib qui contiennent le mot « ranum » ou le mot « cox » ; celle de la troisième ligne affiche les lignes du fichier mes-textes qui commencent par un point (^\.), suivi d’un caractère minuscule compris soit parmi les premières lettres de l’alphabet jusqu’à k, soit parmi les dernières à partir de t, mais pas entre l et s ( ([a-k]|[t-z]) ), suivi d’un caractère minuscule quelconque, suivi d’un espace.

La plupart des langages de programmation modernes procurent un ou plusieurs paquetages d’expressions régulières, notamment pour celles qui obéissent à la norme Posix[4] à laquelle on se reportera pour une description détaillée de laur syntaxe. Le langage que nous utilisons pour ce cours, Scheme, et plus particulièrement le compilateur Bigloo, offre en outre des moyens de construire son propre analyseur de grammaires régulières, qui permettra de reconnaître le langage que l’on aura ainsi défini et d’en analyser les textes.

Outre le livre désormais familier de MM. Hopcroft, Ullmann et Motwani[3], l’excellent ouvrage de Jeffrey E. F. Friedl Maîtrise des expressions régulières [2] sera précieux pour le lecteur désireux d’approfondir la sujet. Il existe en français un petit guide pratique bien fait par Bernard Desgraupes : Expressions régulières – Le Guide de survie [3] L’article de Wikipédia, outre qu’il traduit (à mon avis malheureusement) regular expression par expression rationnelle, n’est pas excellent.

*Premiers repères théoriques — Opérations sur les langages

Rappelons en quel sens nous employons le mot langage : l’ensemble des mots acceptés par un automate, ou qui correspondent à un modèle dénoté par une expression régulière équivalente à cet automate, constitue le langage reconnu par un automate reconnu par l’automate. De façon similaire, un langage est dit reconnaissable s’il existe un automate qui le reconnaît, ou une expression régulière qui le dénote. Un tel langage sera appelé langage régulier.

Les opérateurs utilisés dans les expressions régulières réalisent des opérations sur les langages reconnus par elles. Ces opérations sont au nombre de trois (on rappelle que є désigne le mot vide, qui ne contient aucun caractère) :

**Union

L’union de deux langages L et M, notée L ∪ M, est l’ensemble des mots qui sont soit dans L, soit dans M, soit dans les deux. Ainsi, si L = є, 00, 001, 111 et M = 11, 001, alors L ∪ M = є, 00, 001, 111, 11.

**Concaténation

La concaténation de deux langages L et M, notée L.M ou LM, est l’ensemble des mots formés de la concaténation d’un mot quelconque de L avec un mot quelconque de M. Ainsi, avec nos deux langages de l’alinéa précédent, L = є, 00, 001, 111 et M = 11, 001, LM = 11, 001, 0011, 00001, 00111, 001001, 111111, 111001.

**Fermeture

La fermeture de Kleene (Kleene closure), ainsi nommée d’après le nom du logicien Kleene, d’un langage L, notée L*, est l’ensemble des mots formés par la concaténation d’un nombre quelconque (éventuellement nul) de mots de L, en admettant les répétitions. Si L = 11, 001, alors L* = є, 11, 001, 11001, 1111001, 1111001001, ... . Cet ensemble est infini.

*Les bases des expressions régulières

Nous allons construire l’algèbre des expressions régulières en partant de ses constituants élémentaires, au nombre de trois :

  1. Les constantes є et sont des expressions régulières qui dénotent respectivement les langages є et , ce que nous écrirons L(є) = є et L(∅) = ∅.
  1. Si a est un symbole quelconque, alors a est une expression régulière qui dénote le langage a, soit L(a) = a.
  1. Une variable notée L représente un langage quelconque.

La construction comporte quatre étapes :

  1. Si E et F sont des expressions régulières, E + F est une expression régulière qui dénote l’union de L(E) et de L(F) : L(E + F) = L(E) ∪ L(F).
  1. Si E et F sont des expressions régulières, EF est une expression régulière qui dénote la concaténation de L(E) et de L(F) : L(EF) = L(E)L(F), qui peut aussi se noter : L(E.F) = L(E).L(F).
  1. Si E est une expression régulière, E* est une expression régulière qui dénote la fermeture de L(E) : L(E*) = (L(E))*.
  1. Si E est une expression régulière, (E) est une expression régulière qui dénote le même langage que E : L((E)) = L(E).

**Exemples commentés

*Analyser et décomposer un URL

L’exemple suivant est un programme qui utilise les expressions régulières conformes à la norme Posix de Bigloo pour décomposer le texte de l’URL analysé en ses différents éléments syntaxiques pour un traitement ultérieur. Ce faisant on aura, en prime, vérifié la correction syntaxique de l’URL. Cette opération de vérification, d’analyse et de décomposition d’un texte en éléments syntaxiques est désignée, dans le jargon des informaticiens, par le vocable anglais to parse.

**Syntaxe des URL

L’URL d’un site Web, tel http://www.laurentbloch.org/spip.php?article144 est composé de la façon suivante :

  1. le nom du protocole de communication, qui dans le cas d’un site Web est soit http (Hypertext Transfer Protocol), soit https, version de ce protocole sécurisée par le protocole de chiffrement SSL ;
  2. la chaîne de caractères :// ;
  3. entre :// et le prochain caractère / se trouve écrit le nom du serveur :
    1. sur un réseau local ce peut être un simple nom, par exemple agathe,
    2. mais sur l’Internet c’est un nom de domaine (ce pourrait être aussi une adresse IP, mais cette pratique n’est pas conseillée et nous ne l’étudierons pas),
    3. un nom de domaine est (pour l’instant, parce que les règles sont en train de changer) composé de mots séparés par des points, par exemple www.laurentbloch.org,
    4. le dernier mot (org) est composé de deux, trois ou quatre caractères alphabétiques, c’est l’identifiant du domaine de premier niveau (Top Level Domain), qui est soit national (fr pour la France, be pour la Belgique, dz pour l’Algérie), soit générique (org, com, info...),
    5. les mots précédents, qui sont au gré du propriétaire du domaine, sont composée de caractères alphabétiques latins (non composés, c’est-à-dire sans accents ni cédilles), de chiffres arabes et éventuellement d’un ou plusieurs tirets, à l’exclusion de tout autre caractère, les caractères alphabétiques peuvent être minuscules ou majuscules ;
  4. derrière le nom du serveur vient, de façon facultative, le caractère :, suivi d’un numéro de port, nombre de l’intervalle [0,65535] ;
  5. derrière le nom du serveur (ou le numéro de port facultatif) vient, de façon facultative, un caractère /, suivi ou non du chemin sur le serveur du fichier que l’on veut afficher ; ce chemin est constitué de noms qui obéissent à une syntaxe plus souple que les noms de domaines, nous n’en ferons pas l’analyse.

**Le programme d’analyse

  1. (module verif-url
  2.    (main analyse-arg))
  3. ;;
  4. (define (analyse-arg args)
  5.    (let* ((chaine (cadr args))
  6.           (regexp (string-append "^http(s)?://"
  7.                                  "(([a-zA-Z0-9-]+\\.){1,5}"
  8.                                  "[a-zA-Z]{2,4})(:\\d+)?(/(.*)?)?$"))
  9.           (result (pregexp-match regexp chaine)))
  10.       (if result
  11.           (let ((ssl    (cadr result))
  12.                 (hote   (caddr result))
  13.                 (port (let ((ce-port (car (cddddr result))))
  14.                          (if ce-port
  15.                              (substring ce-port 1
  16.                                         (string-length ce-port)) )))
  17.                 (chemin (let ((ce-chemin (cadr (cddddr result))))
  18.                            (or ce-chemin #unspecified))))
  19.              (print "La chaine a analyser : " chaine)
  20.              (print "SSL ? " ssl)
  21.              (print "Le site hote : " hote)
  22.              (print "Le port : " port)
  23.              (print "Le chemin : " chemin))
  24.           (print chaine " : pas un url"))))

Télécharger

Le texte chaine est confronté à l’expression régulière regexp pour vérifier qu’il est une expression du langage qu’elle dénote. Détaillons un peu l’expression régulière :

^http(s)?://(([a-zA-Z0-9-]+\\.){1,5}[a-zA-Z]{2,4})(:\\d+)?(/(.*)?)?$

  1. Les expressions http et :// dénotent elles-mêmes : le texte doit contenir, littéralement, http et ://.
  2. L’expression http est précédée du caractère ^, nommé ancre de début, qui reconnaît le début de texte, c’est-à-dire qu’il stipule que le texte reconnu par l’expression qu’il précède doit figurer au début du texte : http:// ne doit être précédé, dans chaine, par aucun caractère.
  3. La parenthèse ouvrante qui suit http est le début d’une paire de parenthèses capturantes : le texte reconnu par la sous-expression contenue dans la première paire de parenthèses capturantes sera conservé dans une première variable, numérotée 1, le texte reconnu par la sous-expression de la seconde paire conservé dans une seconde variable, numérotée 2, et ainsi de suite. Au sein de l’expression régulière, je pourrai invoquer une telle variable par son numéro, précédé d’une barre oblique inverse redoublée pour des raisons syntaxiques [4], \1 s’il s’agit de la première. Les paires de parenthèses sont ordonnées de la première à la dernière selon l’ordre d’apparition de leur parenthèse ouvrante, de la gauche vers la droite. Si le texte de chaine est reconnu, Bigloo renverra comme résultat une liste (nommée ici result) dont le premier élément (car result) sera le texte entier de chaine lui-même, le second élément (cadr result) la sous-chaîne reconnu par la première paire de parenthèses capturantes, ainsi de suite.

Dans un langage comme Perl, les sous-chaînes reconnues par les paires de parenthèses capturantes successives seraient stockées dans des variables nommées respectivement $1, $2, etc. En Java, la chaîne reconnue entière serait dans MatcherObj.group(), et les sous-chaînes seraient stockées dans MatcherObj.group(1), MatcherObj.group(2), etc.

  1. Entre http et ://, l’expression (s) ? comporte donc une paire de parenthèses capturantes. Le caractère ? signifie que l’expression encadrée par les parenthèses peut figurer zéro ou une fois dans la chaîne analysée, en effet le préfixe de l’URL d’un site Web peut être https ou http selon qu’il est ou non sécurisé par le protocole SSL.
  2. La première paire de crochets [ ] encadre une classe de caractèresclasse de caractères ; le signe + qui suit cette classe de caractères signifie que l’on doit avoir ici dans le texte au moins un caractère de la classe spécifiée. Cette sous-expression reconnaît un élément du nom du qsite, à l’exclusion du dernier, le nom du domaine de premier niveau.
  3. Derrière le signe + l’expression \. reconnaît un point, destiné à séparer l’élément du nom du site qui vient d’être reconnu de son successeur.
  4. Derrière la seconde parenthèse fermante vient le quantificateur 1,5 qui indique que devant le nom de domaine de premier niveau nous voulons au moins 1 et au plus 5 éléments séparés pas des points.
  5. Puis vient le nom de domaine de premier niveau, composé d’au moins 2 et au plus 4 caractères strictement alphabétiques, et suivi de la troisième parenthèse fermante, qui capturera le nom du site.
  6. Derrière la troisième parenthèse fermante commence une quatrième paire de parenthèses capturantes, suivie du caractère ?, qui signifie que le texte éventuellement reconnu par la sous-expression entre parenthèses doit figure zéro ou une fois ; il s’agit ici en l’occurrence du numéro de port facultatif qui peut suivre le nom du site dans un URL.
  7. L’expression «  : » qui suit la parenthèse ouvrante qui commence la quatrième paire de parenthèses capturantes dénote elle-même «  : » il faut ici «  : », si l’URL comporte un numéro de port explicite.
  8. L’expression \d+ se décompose comme suit : \d dénote un chiffre (digit en anglais, c’est équivalent à [0-9]) ; \d+ signifie donc « au moins un chiffre » qui sera un élément du numéro de port ; la barre oblique inverse est doublée parce que dans Bigloo les expressions régulières sont représentées dans des chaînes de caractères, dont la sémantique confère à la barre oblique inverse \ une signification particulière, et où \ signifie « le caractère barre oblique inverse lui-même ». En Perl cette expression s’écrirait \d+ ; en Java, \d+, comme en Bigloo, pour les mêmes raisons.
  9. L’expression entre parenthèses (/(.*) ?) ? dénote « une barre oblique suivie de zéro ou plusieurs (*) caractères quelconques (.) », qui seront le chemin (facultatif) de la page sur le site ; cette expression est suivie d’un ?, elle peut apparaître zéro ou une fois ; comme elle est enclose dans la cinquième paire de parenthèses capturantes, elle sera renvoyée, si elle est reconnue, comme le (cadddr result) dans notre programme.
  10. Le dernier caractère de notre expression régulière est $, nommé ancre de fin fin, qui reconnaît la fin de texte, c’est-à-dire que le texte reconnu par l’expression qui le précède doit terminer le texte, il ne doit y avoir aucun caractère derrière l’URL.

Voici un exemple d’utilisation de ce programme :

*Parenthèses : grouper, capturer

Avec egrep les parenthèses servent à gouper des expressions séparées par une alternative, mais avec un langage de programmation les parenthèses groupent et capturent. C’est pratique parce qu’ainsi on peut faire quelque-chose du texte reconnu :

  1. (module grouper-capturer
  2.    (main analyse-fichier))
  3. ;;
  4. (define (analyse-fichier args)
  5.    (let ((un-fichier (cadr args)))
  6.       (call-with-input-file un-fichier lire-des-lignes)))
  7. ;;
  8. (define (lire-des-lignes flux)
  9.    (let boucle ((ligne (read-line flux)))
  10.       (if (eof-object? ligne)
  11.           ligne
  12.           (begin
  13.              (analyse ligne)
  14.              (boucle (read-line flux))))))
  15. ;;
  16. (define (analyse ligne)
  17.    (let* ((regexp "(ranum|cox)")
  18.           (result
  19.            (if (pregexp-match regexp ligne)
  20.                (pregexp-replace* regexp ligne "--\\1--"))))
  21.       (if result (print ligne #\newline result))))

Télécharger

*Signaler les doublons

Voici un programme qui lit un texte et y repère les mots identiques successifs, possibles fautes de frappe ou répétitions significatives :

  1. (module elimine-doublons
  2.    (main analyse-fichier))
  3. ;;
  4. (define (analyse-fichier args)
  5.    (let ((un-fichier (cadr args)))
  6.       (call-with-input-file un-fichier lire-des-paragraphes)))
  7. ;;
  8. (define (lire-des-paragraphes flux)
  9.    (let boucle ((paragraphe (lire-un-paragraphe flux)))
  10.       (if (eof-object? paragraphe)
  11.           #f
  12.           (begin
  13.              (analyse paragraphe)
  14.              (boucle (lire-un-paragraphe flux))))))
  15. ;;
  16. (define (lire-un-paragraphe flux)
  17.    (let boucle ((paragraphe "")
  18.                 (ligne (read-line flux)))
  19.       (if (eof-object? ligne)
  20.           ligne
  21.           (if (string=? ligne "")
  22.               paragraphe
  23.               (boucle (string-append paragraphe " " ligne)
  24.                       (read-line flux))))))
  25. ;;
  26. (define (analyse paragraphe)
  27.    (let* ((regexp "(\\S+) \\1")
  28.           (result (pregexp-replace* regexp paragraphe "**\\1 \\1**")))
  29.       (print result)))

Télécharger

Fort des commentaires de l’exemple précédent, l’expression régulière de celui-ci ne devrait pas être trop difficile à interpréter :

(\\S+) \\1

L’expression \s reconnaît tout ce qui est un espace au sens large : espace, espace insécable, tabulation horizontale ou verticale, saut de ligne ou de page, etc. La barre oblique inverse est doublée en Bigloo pour la même raison qu’à la section précédente. L’expression \S (S majuscule !) reconnaît tout ce qui n’est pas un espace. \S+ reconnaît donc toute séquence d’au moins un caractère non-blanc.

Comme l’expression \S+ est entre parenthèses, le contenu de la dernière chaîne qu’elle aura reconnue sera conservé dans la variable numérotée 1. Au sein de l’expression régulière, je pourrai invoquer cette variable par son numéro, \1.

Tout devient clair : (\S+) reconnaît toute chaîne non interrompue par un espace, et \1 reconnaît toute occurrence de cette même chaîne qui vient d’être reconnue : il s’agit donc d’un doublon.

Un doublon peut-être légitime : nous nous voyons dans la glace. Aussi nous contentons-nous de l’afficher, mis en valeur entre deux paires d’astérisques.

Attention, ce programme est perfectible, il engendre des faux positifs, en signalant comme doublons les préfixes de mots qui sont aussi des suffixes du mot précédent. La correction est laissée en exercice pour le délassement du lecteur.

*Équivalence expression régulière-NFA-DFA

Démontrer l’équivalence entre les langages réguliers (dénotés par les expression régulière) et la classe des langages reconnus par les NFA et les DFA demande de démontrer d’une part, que tout langage dénoté par une expression régulière est reconnu par un automate à états fini, d’autre part que tout langage reconnu par un automate est dénoté par une expression régulière.

Nous emprunterons les démonstrations à nos guides habituels, MM. Hopcroft, Ullmann et Motwani.

**De l’automate à l’expression régulière

Théorème

Si L(A) est le langage reconnu par un DFA A, alors il existe une expression régulière R qui dénote un langage L(R) tel que L(R) = L(A).

Démonstration :

Soit $n$ le nombre d’états de $A$. Nous savons, par la définition des automates finis, que $n$ existe et qu’il est fini.

Notons $R_{ij}^{(k)}$ le nom d’une expression régulière qui dénote le langage défini par l’énumération des éléments de l’ensemble des mots $w$ tels que $w$ est l’étiquette d’un chemin de l’état $i$ à l’état $j$ dans $A$, et tels que ce chemin ne passe par aucun nœud intermédiaire dont le numéro soit supérieur à $k$.

Nous construirons par induction l’ensemble des expressions régulières $R_{ij}^{(k)}$, en allant de $k=0$ à $k=n$, en notant que pour $k=n$ il n’y a aucune contrainte sur les numéros des nœuds intermédiaires, puisqu’aucun ne peut avoir un numéro supérieur à $n$.

Base de l’induction : Pour $k=0$ : puisque les nœuds susceptibles d’être intermédiaires sont numérotés à partir de 1, les chemins acceptables dans ce cas là ne peuvent avoir aucun nœud intermédiaire, ce qui limite aux chemins directs entre un nœud $i$ et un nœud $j$, et aux chemins de longueur nulle à partir d’un nœud $i$. Si $i ≠ j$, seul le premier cas est possible.

Nous devons donc trouver dans le DFA $A$ les symboles a tels que pour l’entrée a il y ait une transition de l’état $i$ à l’état $j$.

 s’il n’y a aucun symbole a qui satisfasse cette condition :
$R_{ij}^{(0)}=\emptyset$

 s’il y a un symbole $a$ unique qui satisfait cette condition :
$R_{ij}^{(0)}=a$

 s’il y a k symboles $a_1, a_2, ..., a_k$ qui satisfont cette condition :
$R_{ij}^{(0)}=a_1+a_2+...+a_k$

Si i = j, les chemins valides sont les chemins de longueur 0, qui bouclent de i à lui-même. Le chemin de longueur nulle est décrit par l’expression régulière є. Nous ajouterons donc є à chacune des trois expressions trouvées ci-dessus pour $R_{ij}^{(0)}$ selon les cas ; ces expressions deviennent respectivement $\epsilon$, $\epsilon + a$ et $\epsilon + a_1 + a_2 + ... + a_k$.

Induction : Supposons qu’il y ait un chemin de l’état i à l’état j qui ne passe par aucun état de numéro supérieur à k. Deux cas sont possibles :

  1. Le chemin considéré ne passe pas par l’état k. Dans ce cas, l’étiquette du chemin appartient au langage de $R_{ij}^{(k−1)}$.
  2. Le chemin considéré passe au moins une fois par l’état k. Nous pouvons alors couper le chemin en plusieurs chemins partiels délimités par les passages par l’état k : le premier de ces chemins partiels va de i à k sans passer par k, le dernier va de k à j sans passer par k, et tous les autres vont de k à k sans passer par k. L’ensemble des étiquettes de ces chemins partiels constitue le langage dénoté par l’expression régulière :

$R_{ik}^{(k-1)}(R_{kk}^{(k-1)})^* R_{kj}^{(k-1)}$

où la première expression représente la partie du chemin qui va de i à k la première fois, la seconde représente la partie (présente zéro, une ou plusieurs fois) qui va de k à k lui-même, la troisième représente la partie fienale, qui va de k à j.

La combinaison des expressions qui décrivent les deux types de chemins identifiés ci-dessus s’écrit, pour les étiquettes de tous les chemins de l’état i à l’état j qui ne traversent aucun état de numéro supérieur à k :

$R_{ij}^{(k)} = R_{ij}^{(k-1)} + R_{ik}^{(k-1)}(R_{kk}^{(k-1)})^* R_{kj}^{(k-1)}$

Puisque cette expression s’écrit pour un k donné uniquement en fonction d’expressions avec k plus petit, nous pouvons la calculer pour tout valeur de k, et notamment pour k = n, soit Rij(n), et ce pour tout i et pour tout j. Soit 1 le numéro de l’état initial de l’automate, et pour un ensemble quelconque d’états acceptants, l’expression régulière qui dénote le langage de l’automate est la somme (l’union) de toutes les expressions $R_{1j}^{(n)}$ telles que l’état j soit un état acceptant.

**De l’expression régulière à l’automate

Théorème

Si L = L(R) est le langage dénoté par une expression régulière R, alors il existe un automate fini A qui reconnaît un langage L(A) tel que L = L(A).

On introduit la notion de є-NFA, une variété de NFA qui admet des chemins étiquetés par le mot vide є.

Démonstration :

Hypothèse de l’induction :

Nous allons montrer que L = L(A) pour un є-NFA A avec :

  1. exactement un état acceptant ;
  2. aucun arc vers l’état initial ;
  3. aucun arc partant de l’état acceptant.

Cette démonstration se fera par induction sur R, en suivant la définition récursive des expressions régulières vue ci-dessus.

Base de l’induction :

  1. Construction de l’automate pour l’expression régulière є : le langage de l’automate qui correspond à cette expression est є, puisque le chemin unique de l’état initial à l’état acceptant est étiqueté є.
  2. Construction de l’automate pour ∅ : il n’y a pas de chemin de l’état initial à l’état acceptant, donc le langage de cet automate est ∅.
  3. Construction de l’automate pour a : le langage de cet automate est a = L(a).

Figure 2 : Automates pour є, ∅ et a.

On vérifie que ces trois automates vérifient les trois conditions de l’hypothèse de l’induction.

Induction :

La figure 3 montre les trois parties de l’induction. On suppose que le théorème est vrai pour les sous-expressions de l’expression considérée, c’est-à-dire que les langages dénotés par ces sous-expressions sont aussi les langages de є-NFA avec un seul état acceptant.

Figure 3 : Automates pour la construction de l’automate є-NFA

  1. Pour l’expression R + S qui dénote l’union des sous-expressions R et S c’est la figure 3 (1) qui s’applique. En partant de l’état initial de l’automate qui en représente l’union, nous pouvons aller soit vers l’état initial de l’automate qui reconnaît le langage de R, soit vers l’état initial de celui qui reconnaît le langage de S, en suivant un chemin étiqueté par un mot de L(R) ou de L(S), respectivement. Une fois atteint l’état acceptant de R ou de S, selon le cas, il est possible de suivre l’un des є-arcs vers l’état acceptant du nouvel automate.
  2. Pour l’expression RS qui dénote la concaténation des sous-expressions R et S c’est la figure 3 (2) (Automates pour la construction de l’automate є-NFA) qui s’applique. L’état initial du premier automate devient l’état initial de l’ensemble, cependant que l’état acceptant du second devient l’état acceptant de l’ensemble, ce qui signifie que les seuls chemins de l’état initial à l’état acceptant doivent d’abord passer par l’automate de R en suivant un chemin étiqueté par un mot de L(R), puis passer par l’automate de S en suivant un chemin étiqueté par un mot de L(S). Ainsi, les chemins de l’automate de la figure 3 sont tous les chemins étiquetés par des mots de L(R)L(S), et uniquement eux.
  3. Pour l’expression R* qui dénote la fermeture de Kleene de la sous-expression R, c’est la figure 3 (3) qui s’applique. Deux types de chemins sont possibles :
    1. Directement de l’état initial à l’état final par un chemin étiqueté є. Ce chemin nous fait accepter є, qui est dans L(R*), quelle que soit l’expression R.
    2. Vers l’état initial de l’automate de R, par cet automate, une ou plusieurs fois, puis vers l’état acceptant. Cet ensemble de chemins nous permet d’accepter les mots de L(R), L(R)L(R), L(R)L(R)L(R), etc., en décrivant ainsi tous les mots de L(R*) à l’exception de є, décrit par le cas précédent.
  4. Pour mémoire, l’automate de R est aussi l’automate de (R), puisque les parenthèses ne modifient pas le langage dénoté par l’expression.

L’automate ainsi construit satisfait les trois conditions de l’hypothèse d’induction : un seul état acceptant, sans arcs vers l’état initial ni depuis l’état acceptant.