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

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

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

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

Langage quotient

Un langage (formel) sur alphabet ${\displaystyle A}$ est un ensemble de mots sur ${\displaystyle A}$.

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

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

Les formules suivantes sont utiles :

${\displaystyle \varepsilon ^{-1}L=L}$ ; ${\displaystyle (uv)^{-1}L=v^{-1}u^{-1}L}$

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

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

Expressions régulières

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

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

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

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

1. ${\displaystyle L(0)=\emptyset }$, ${\displaystyle L(1)=\{\varepsilon \}}$ (le mot vide),${\displaystyle L(a)=\{a\}}$ pour ${\displaystyle a\in A}$
2. ${\displaystyle L(e+f)=L(e)\cup L(f)}$, ${\displaystyle L(e\cdot f)=L(e)L(f)}$, et ${\displaystyle 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 ${\displaystyle (a+b)^{*}}$ et ${\displaystyle (a^{*}b)^{*}a^{*}}$ dénotent le même langage.

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

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

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

${\displaystyle L(d_{u}(e))=u^{-1}L(e)}$,

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

• La dérivée par rapport à une lettre ${\displaystyle a}$ est définie par :
  1. ${\displaystyle d_{a}(0)=d_{a}(1)=0}$, ${\displaystyle d_{a}(a)=1}$, ${\displaystyle d_{a}(b)=0}$ pour toute lettre ${\displaystyle b\neq a}$
  2. ${\displaystyle d_{a}(e+f)=d_{a}(e)+d_{a}(f)}$, ${\displaystyle d_{a}(e^{*})=d_{a}(e)\cdot e^{*}}$ et

  ${\displaystyle 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 ${\displaystyle ua}$ est définie par récurrence par la composition des dérivations par :

${\displaystyle d_{ua}=d_{a}\circ d_{u}}$,

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

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

La formule du produit s'écrit alors

${\displaystyle 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

${\displaystyle 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

Considérons l'expression

${\displaystyle (a^{*}b)^{*}a^{*}}$

Sa dérivée, par rapport à la lettre ${\displaystyle a}$, est

${\displaystyle {\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

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

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

Finitude de l'ensemble des dérivées

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

L'automate des expressions dérivées

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

${\displaystyle q\cdot a=d_{a}(q)}$.

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

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

Exemple

Considérons l'expression

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

Notons

${\displaystyle 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 ${\displaystyle g}$ et ${\displaystyle h}$ sont terminaux. Il est reproduit ci-contre^[5].

Calcul pratique

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

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

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

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

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

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

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

${\displaystyle 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

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

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

Exemple

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

Notes et références

Bibliographie

• 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