Dérivée de Brzozowski

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}}$.

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}$.

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.

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.

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}$.

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.

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

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)}$.

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

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}$ son terminaux. Il est reproduit ci-contre[5].

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].

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)^{*}}$.

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

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)}$.

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 :