Dérivée de Brzozowski

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

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

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

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

La concaténation de deux mots $w_{1}$ et $w_{2}$ est le mot constitué des lettres de $w_{1}$ suivies des lettres de $w_{2}$ . On le note par simple juxtaposition $w_{1}w_{2}$ .

Langage quotient modifier

Article détaillé : langage formel.

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

Pour un langage $L$ sur un alphabet $A$ et un mot $u$ sur $A$ , on appelle langage quotient (aussi langage résiduel ou quotient à gauche) de $L$ par rapport à $u$ l'ensemble des mots $x$ tels que $ux$ est un mot de $L$ ; on le note $u^{-1}L$ . Formellement,

u^{-1}L=\{x\in A^{*}\mid ux\in L\}

.

Les formules suivantes sont utiles :

\varepsilon ^{-1}L=L

;

(uv)^{-1}L=v^{-1}u^{-1}L

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

X^{-1}L=\bigcup _{u\in X}u^{-1}L

.

Expressions régulières modifier

Article détaillé : expression rationnelle.

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

Les symboles $0$ , $1$ , et toute lettre $a$ pour $a\in A$ sont de expressions régulières ;
si $e$ et $f$ sont des expressions régulières, alors $e+f$ , $e\cdot f$ (aussi noté $ef$ ) et $e^{*}$ sont des expressions régulières;
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

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 $0$ et $1$ , et la représentation de l’union par le symbole d'addition

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

$L(0)=\emptyset$ , $L(1)=\{\varepsilon \}$ (le mot vide), $L(a)=\{a\}$ pour $a\in A$
$L(e+f)=L(e)\cup L(f)$ , $L(e\cdot f)=L(e)L(f)$ , et $L(e^{*})=L(e)^{*}$ .

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 $(a+b)^{*}$ et $(a^{*}b)^{*}a^{*}$ dénotent le même langage.

Dérivée d'une expression régulière modifier

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

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

L(d_{u}(e))=u^{-1}L(e)

,

où, comme rappelé ci-dessus, on a $u^{-1}L=\{x\in A^{*}\mid ux\in L\}$ .

La dérivée par rapport à une lettre $a$ est définie par :
1. $d_{a}(0)=d_{a}(1)=0$ , $d_{a}(a)=1$ , $d_{a}(b)=0$ pour toute lettre $b\neq a$
2. $d_{a}(e+f)=d_{a}(e)+d_{a}(f)$ , $d_{a}(e^{*})=d_{a}(e)\cdot e^{*}$ et
$d_{a}(e\cdot f)={\begin{cases}d_{a}(e)\cdot f&{\text{ si }}\varepsilon \notin L(e)\\d_{a}(e)\cdot f+d_{a}(f)&{\text{ sinon. }}\end{cases}}$
La dérivée par rapport à un mot $ua$ est définie par récurrence par la composition des dérivations par :

d_{ua}=d_{a}\circ d_{u}

,

avec $d_{\varepsilon }=\operatorname {Id}$ . 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 $c$ et appelée le terme constant de l'expression^[4], est définie par aussi par récurrence sur l'expression comme suit :

$c(1)=1$ , $c(0)=c(a)=0$ , pour toute lettre $a$ ,
$c(e+f)=max(c(e),c(f))$ , $c(ef)=c(e)c(f)$ et $c(e^{*})=1$ .

La formule du produit s'écrit alors

d_{a}(e\cdot f)=d_{a}(e)\cdot f+c(e)\cdot d_{a}(f)

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

0+e\equiv e+0\equiv e,0\cdot e\equiv e\cdot 0\equiv 0,1\cdot e\equiv e\cdot 1\equiv 1

.

Exemple modifier

Considérons l'expression

(a^{*}b)^{*}a^{*}

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

{\begin{aligned}d_{a}{\bigl (}(a^{*}b)^{*}a^{*}{\bigr )}&=d_{a}{\bigl (}(a^{*}b)^{*}{\bigr )}a^{*}+c((a^{*}b)^{*})d_{a}(a^{*})=d_{a}{\bigl (}(a^{*}b){\bigr )}(a^{*}b)^{*}a^{*}+1\cdot 1\cdot a^{*}\\&={\bigl (}d_{a}(a^{*})b+1\cdot d_{a}(b){\bigr )}(a^{*}b)^{*}a^{*}+a^{*}=(a^{*}b+1\cdot 0)(a^{*}b)^{*}a^{*}=a^{*}b(a^{*}b)^{*}a^{*}+a^{*}.\end{aligned}}

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

Propriétés modifier

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

Propriété — Pour toute expression régulière $e$ et tout mot $u$ , on a : $L(d_{u}(e))=u^{-1}L(e)$ .

Pour un langage rationnel $L$ , la famille de langages $u^{-1}L$ , où $u$ parcourt l’ensemble de tous les mots, est finie. Cela n'implique pas que la famille des expressions $d_{u}(e)$ dérivées de $e$ soit finie, car on peut avoir une infinité d'expressions pour le même langage !

Finitude de l'ensemble des dérivées modifier

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 $e+f$ et $f+e$ sont considérées comme équivalentes (commutativité), de même $e+e\equiv e$ (idempotence) et $(e+f)+g\equiv (e+(f+g)$ (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

Soit $e$ une expression régulière sur un alphabet $A$ , et soit $Q=\{d_{u}(e)\mid u\in A^{*}\}$ 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 $L(e)$ . Pour cela, on définit la fonction de transition, pour un état $q$ et une lettre $a$ , par

q\cdot a=d_{a}(q)

.

Ainsi, si $q=d_{u}(e)$ pour un mot $u$ , alors $q\cdot a=d_{a}(d_{u}(e))=d_{ua}(e)$ . L'état initial de l'automate est l'expression $e$ , les états terminaux sont les expressions $f$ telles que le terme constant est 1.

Cet automate, aussi appelé automate de Brzozowski reconnait le langage $L(e)$ .

Exemple modifier

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

Considérons l'expression

e=(a+b)^{*}ab(a+b)^{*}

Notons

f=d_{a}(e)=e+b(a+b)^{*},g=d_{ab}(e)=d_{b}(f)=e+(a+b)^{*},h=d_{aba}(e)=d_{a}(g)=e+b(a+b)^{*}+(a+b)^{*}

.

L'automate obtenu a quatre états, les états $g$ et $h$ sont terminaux. Il est reproduit ci-contre^[5].

Calcul pratique modifier

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

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

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

$d_{a}(0)=d_{a}(1)=0,d_{a}(a)=1$ et $d_{a}(b)=0$ pour $b\neq a$ ;
$d_{a}(e+f)=d_{a}(e)\cup d_{a}(f)$ , $d_{a}(e^{*})=d_{a}(e)e^{*}$ et $d_{a}(e\cdot f)=d_{a}(e)\cdot f\cup c(e)d_{a}(f)$ .
De plus, $d_{ua}(e)=d_{a}(d_{u}(e))$ pour tout mot $u$ .

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

e=(a+b)^{*}ab(a+b)^{*}

considéré comme le produit de $(a+b)^{*}$ par $ab(a+b)^{*}$ , on obtient

d_{a}(e)=(d_{a}(a+b)^{*})ab(a+b)^{*}\cup d_{a}(ab(a+b)^{*})=e\cup b(a+b)^{*}

.

Construction de l'automate modifier

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

L'ensemble des termes atomiques obtenus en dérivant $e$ est l'ensemble des termes dérivés de $e$ . 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 $|e|$ états, où $|e|$ est la taille de $e$ .

L'automate déduit des termes dérivés a pour états les termes dérivés, et comme plus haut l'expression $e$ pour état initial et chaque expression $f$ telle que $c(f)=1$ . Les transitions sont les triplets $(f,a,g)$ tels que $g$ est un terme figurant dans $d_{a}(f)$ .

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

Exemple modifier

Dans l'exemple ci-dessus, pour $e=(a+b)^{*}ab(a+b)^{*}$ , les termes dérivés sont $e$ , $b(a+b)^{*}$ et $(a+b)^{*}$ . L'automate des termes dérivés est :

Notes et références modifier

↑ Brzozowski 1964.
↑ 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.
↑ On trouve aussi la notation $\partial /\partial u$ , par exemple chez Sakarovitch 2003, p. 149.
↑ Notation et terminologie de Sakarovitch 2003, p. 148.
↑ Sakarovitch 2003, p. 153.
↑ Scott Owens, John H. Reppy et Aaron Turon, « Regular-expression derivatives re-examined », J. Functional Programming, vol. 19, n^o 2,‎ 2009, p. 173-190 (DOI 10.1017/S0956796808007090, lire en ligne).
↑ Sakarovitch 2003, p. 159.
↑ Sakarovitch 2003, p. 159 dit $\mathbb {B}$ -dérivée.

Bibliographie modifier

Janusz A. Brzozowski, « Derivatives of Regular Expressions », Journal of the ACM, vol. 11,‎ 1964, 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, n^o 2,‎ 1996, p. 291-319
Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, 2003, 816 p. (ISBN 2-7117-4807-3, zbMATH 1188.68177)

Portail de l'informatique théorique

[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 $\partial /\partial u$ , 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, n^o 2,‎ 2009, p. 173-190 (DOI 10.1017/S0956796808007090, lire en ligne).

[7] Sakarovitch 2003, p. 159.

[8] Sakarovitch 2003, p. 159 dit $\mathbb {B}$ -dérivée.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]