Dérivée de Brzozowski

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En Informatique théorique, et en particulier en théorie des automates finis, la dérivée de Brzozowski est un outil qui permet de construire un automate fini à partir d'une expression rationnelle ou régulière.

Elle tient son nom de l'informaticien Janusz A. Brzozowski qui, dans un article datant de 1964[1], en a étudié ses propriétés et a démontré que l’algorithme de calcul se termine.

Terminologie[modifier | modifier le code]

La dérivée de Brzozowski s'applique à des expressions rationnelles, en relation avec les notions de langages formels et d'automates finis. On résume ici les définitions de ces notions.

Mots[modifier | modifier le code]

Article détaillé : Mot (mathématiques).

Un alphabet est un ensemble quelconque, en général fini. On appelle lettres ses éléments. Un mot sur l'alphabet est une suite finie de lettres. On appelle mot vide, et on le note , le mot qui ne comporte aucune lettre.

La concaténation de deux mots et est le mot constitué des lettres de suivies des lettres de . On le note par simple juxtaposition .

Langage quotient[modifier | modifier le code]

Article détaillé : langage formel.

Un langage (formel) sur alphabet est ensemble de mots sur .

Pour un langage sur un alphabet et un mot sur , on appelle langage quotient (aussi langage résiduel ou quotient à gauche) de par rapport à l'ensemble des mots tels que est un mot de ; on le note . Formellement,

.

Les formules suivantes sont utiles :

 ;

La notation de langage résiduel est étendue aux parties par

.

Expressions régulières[modifier | modifier le code]

Article détaillé : expression rationnelle.

Soit un alphabet fini. Les expressions régulières sur sont les expressions obtenues par récurrence comme suit :

  1. Les symboles , , et toute lettre pour sont de expressions régulières ;
  2. si et sont des expressions régulières, alors , (aussi noté ) et sont des expressions régulières;
  3. toute expression régulière est obtenue, à partir des expressions atomiques (1), par un nombre fini d'applications des règles de composition (2).

D'autres opérateurs, comme l'intersection ou la négation, sont ajoutées dans les applications aux traitements de textes, ainsi que d'autres extensions qui n'interviennent pas dans le contexte présent.

Langage dénoté par une expression[modifier | modifier le code]

Les expressions régulières servent à décrire de façon concise un langage formel. En particulier, une expression rationnelle (qui est toujours finie) peut décrire un langage infini. Il est important de distinguer le l'expression et le langage qu'elle dénote, puisque qu'un même langage peut être décrit de multiples manières. C'est à cela que servent les symboles et , et la représentation de l’union par le symbole d'addition

Le langage dénoté par une expression est noté . Il est défini par récurrence sur la structure de l'expression comme suit:

  1. , (le mot vide), pour
  2. , , et .

Notons qu'une expression régulière ne dénote qu'un seul langage, mais un même langage peut être dénoté par plusieurs expressions régulières différentes. Par exemple, les expressions et dénotent le même langage.

Dérivée d'une expression régulière[modifier | modifier le code]

La dérivée de Brzozowski (ou dérivée tout court) d'une expression régulière est à nouveau une expression régulière. Le langage dénoté par l'expression dérivée est le quotient gauche (aussi appelé langage dérivé parfois) du langage dénoté par l'expression de départ. Les deux opérations de dérivation opèrent donc « en parallèle », l'une sur les expressions, l'autre sur les langages. Autant les expressions peuvent se manipuler par des algorithmes effectifs, autant la manipulation des langages n'est réalisable qu’indirectement, par une de leurs représentations finies.

Des applications concrètes de ces algorithmes ont vu le jour dans le contexte de l'analyse de textes XML[2].

Définition[modifier | modifier le code]

Les dérivées sont indexées par un mot sur l'alphabet . Le but est d'obtenir, pour un mot et une expression , une nouvelle expression telle que le langage soit le langage des mots de privés du préfixe . La dérivée par rapport à un mot est notée [3]. L'objectif est donc de préserver la relation

,

où, comme rappelé ci-dessus, on a .

  • La dérivée par rapport à une lettre est définie par :
    1. , , pour toute lettre
    2. , et
  • La dérivée par rapport à un mot est définie par récurrence par la composition des dérivations par :
,

avec . La formule pour le produit peut s'écrire autrement en introduisant une fonction auxiliaire qui teste si le langage dénoté par une expression contient ou non le mot vide. Cette fonction, notée et appelée le terme constant de l'expression[4], est définie par aussi par récurrence sur l'expression comme suit :

  1. , , pour toute lettre ,
  2. , et .

La formule du produit s'écrit alors

Le résultat est le même sous réserve d'appliquer les identifications dites triviales, c'est-à-dire de supprimer les occurrences de 0 et de 1 où on peut le faire, en d'autres termes en utilisant les relations

.

Exemple[modifier | modifier le code]

Considérons l'expression

Sa dérivée, par rapport à la lettre , est

Pour plus de détails, on a gardé longuement les 0 et les 1 dans l'expression.

Propriétés[modifier | modifier le code]

La propriété première est la formule suivante, valable pour toute expression et tout mot :

Propriété — Pour toute expression régulière et tout mot , on a :.

Pour un langage rationnel , la famille de langages , où parcourt l’ensemble de tous les mots, est finie. Cela n'implique pas que la famille des expressions dérivées de soit finie, car on peut avoir une infinité d'expressions pour le même langage !

Finitude de l'ensemble des dérivées[modifier | modifier le code]

Un théorème tout à fait remarquable, et qui est le résultat principal de l'article de Brzozowski de 1964, stipule que l'ensemble des dérivées d'une expression est finie sous réserve que l'on applique quelques simplifications aux formules, en plus de la suppression des 0 et 1. Ainsi, les deux expressions et sont considérées comme équivalente (commutativité), de même (idempotence) et (associativité).

Théorème (Brzozowski) — L'ensemble des dérivées d'une expression rationnelle est finie modulo l'identification d'expressions par les règles d'associativité, de commutativité, d'idempotence, et les identités faisant intervenir 0 et 1.

L'automate des expressions dérivées[modifier | modifier le code]

Soit une expression régulière sur un alphabet , et soit l'ensemble de ses expressions dérivées. Cet ensemble — qui est fini par le théorème de Brzozowski — peut être vu comme l’ensemble des états d'un automate déterministe complet qui, de plus, reconnaît le langage . Pour cela, on définit la fonction de transition, pour un état et une lettre , par

.

Ainsi, si pour un mot , alors . L'état initial de l'automate est l'expression , les états terminaux sont les expressions telles que le terme constant est 1.

Cet automate, aussi appelé automate de Brzozowski reconnait le langage .

Exemple[modifier | modifier le code]

Automate des expressions dérivées, par la méthode de Brzozowski.

Considérons l'expression

Notons

.

L'automate obtenu a quatre états, les états et son terminaux. Il est reproduit ci-contre[5].

Calcul pratique[modifier | modifier le code]

Le calcul pratique de l'automate à partir de l’expression demande une représentation commode d'expressions rationnelles, comme peuvent le fournir les arbres ou alors des objets que l'on peut définir dans des langages de programmation évolués qui en permettent une manipulation facile. Ces arbres sont normalisés en supprimant les sommets étiquetés par 0 et 1 là où c'est possible, en faisant un choix pour la commutativité qui consiste par exemple à prendre comme premier terme celui qui est le plus petit lexicographiquement, et pour l'associativité de faire un choix analogue ou de représenter les opérandes non pas sous forme de suite, mais sous la forme d'un ensemble[6].

Extension : l'algorithme d'Antimirov[modifier | modifier le code]

L'automate obtenu par la méthode de Brzozowski décrite ci-dessus est fini, déterministe, complet, mais n'a aucune raison d'être minimal. Il peut donc être victime de l'explosion exponentielle qui le rend impraticable. Une variante de la méthode de Brzozowski remplace la dérivée d'une expression, qui est une somme de termes, par l'ensemble des termes de cette somme. Cette petite modification a pour conséquence que les composants de l’automate se présentent comme des ensembles d'états, chacun présenté par un terme plus petit. La méthode d'Antimirov qui tire profit de cette observation a la propriété d'être non déterministe, mais d'avoir peu d'états (autant que l'automate de Glushkov); de plus, l'identification par les diverses identités de commutation et d'associativité n'est plus nécessaire[7].

Extension de la notion de dérivée[modifier | modifier le code]

Soit une expression régulière sur , et soit une lettre. La dérivée de par rapport à [8] est un ensemble d'expressions régulières, défini récursivement par :

  1. et pour ;
  2. , et .
  3. De plus, pour tout mot .

On identifie ici un ensemble ayant un seul élément avec l'élément qui le compose. Par exemple, pour

considéré comme le produit de par , on obtient

.

Construction de l'automate[modifier | modifier le code]

Automate des termes dérivés, par la méthode d'Antimirov.

L'ensemble des termes atomiques obtenus en dérivant est l'ensemble des termes dérivés de . Ce sont eux qui servent d'états à l'automate reconnaissant le langage. Le langage dénoté par un ensemble d'expressions rationnelles est par définition l'union des langages dénotés par les expressions. L'intérêt de cette dérivation par rapport à celle de Brzozowski réside dans le fait que l'automate obtenu a au plus états, où est la taille de .

L'automate déduit des termes dérivés a pour états les termes dérivés, et comme plus haut l'expression pour état initial et chaque expression telle que . Les transitions sont les triplets tels que est un terme figurant dans .

Antimirov — L'automate déduit des termes dérivées d'une expression rationnelle reconnaît le langage dénoté par , et possède au plus états.

Exemple[modifier | modifier le code]

Dans l'exemple ci-dessus, pour , les termes dérivés sont , et . L'automate des termes dérivés est :

Notes et références[modifier | modifier le code]

  1. Brzozowski 1964.
  2. Pour un exposé historique, voir par exemple C. M. Sperberg-McQueen, Applications of Brzozowski derivatives to XML Schema processing, Extreme Markup Languages 2005, Montréal.
  3. On trouve aussi la notation , par exemple chez Sakarovitch 2003, p. 149.
  4. Notation et terminologie de Sakarovitch 2003, p. 148.
  5. Sakarovitch 2003, p. 153.
  6. Scott Owens, John H. Reppy et Aaron Turon, « Regular-expression derivatives re-examined », J. Functional Programming, vol. 19, no 2,‎ , p. 173-190 (DOI 10.1017/S0956796808007090, lire en ligne).
  7. Sakarovitch 2003, p. 159.
  8. Sakarovitch 2003, p. 159 dit -dérivée.

Bibliographie[modifier | modifier le code]

  • Janusz A. Brzozowski, « Derivatives of Regular Expressions », Journal of the ACM, vol. 11,‎ , p. 481–494 (DOI 10.1145/321239.321249).
  • Valentin M. Antimirov, « Partial Derivatives of Regular Expressions and Finite Automaton Constructions », Theor. Comput. Sci, vol. 155, no 2,‎ , p. 291-319
  • Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, (ISBN 2-7117-4807-3, zbMATH 1188.68177)Document utilisé pour la rédaction de l’article