Option informatique — MP — 2022
4 heures. Calculatrice autorisée.
Ce sujet aborde différents problèmes autour des automates et des expressions rationnelles. On explore dans une première partie des propriétés sur le miroir d’un langage, sur les palindromes et sur les automates correspondants.
On implémente ensuite l’algorithme de déterminisation d’un automate, afin de construire de manière effective l’automate de Brzozowski qui a la propriété d’être minimal.
Dans une deuxième partie, on travaille sur la syntaxe des expressions rationnelles, puis sur une construction de l’expression rationnelle associée à un automate donné, par un algorithme diviser pour régner, dû à Conway, en exploitant une représentation matricielle d’un automate et la construction de l’étoile d’une matrice d’expressions rationnelles.
Enfin, dans une troisième partie, on introduit les dérivées d’Antimirov, qui permettent d’obtenir un automate fini non déterministe avec peu d’états qui reconnait le langage spécifié par une expression rationnelle. Les trois parties sont indépendantes, de difficulté progressive.
Langages et mots
On appelle alphabet tout ensemble fini de lettres. On note généralement l’alphabet {\Sigma}.
On note {\Sigma^\star} l’ensemble de tous les mots formés sur l’alphabet {\Sigma}.
La longueur (ou la taille) d’un mot {w\in\Sigma^\star} est son nombre de lettres et se note {|w|}. Le mot vide, noté {\varepsilon}, est le seul mot de longueur nulle.
Si un mot {w\in\Sigma^\star} est de longueur {|w|=n}, on le note {w=a_0a_1\ldots a_{n-1}}, où les {a_i} sont des lettres de {\Sigma}.
Un langage sur l’alphabet {\Sigma} est un ensemble {L\subset\Sigma^\star}.
L’étoile de Kleene d’un langage {L}, notée {L^\star}, est le plus petit langage qui inclut {L}, qui contient {\varepsilon} et qui est stable par concaténation.
La concaténation de deux langages {L} et {L'} est notée {L\cdot L'}, souvent abrégé en {LL'} lorsqu’il n’y a pas d’ambiguïté.
Automates finis
Un automate fini non déterministe sur un alphabet {\Sigma} est un quadruplet {A=(Q,I,F,T)}, où {Q} est un ensemble fini d’états, {I\subset Q} est le sous-ensemble des états initiaux, {F\subset Q} est le sous-ensemble des états finaux et l’ensemble {T\subset Q\times\Sigma\times Q} est l’ensemble des transitions, étiquetées par les lettres de l’alphabet {\Sigma}.
Si {(q,a,q')\in T}, on note {q\xrightarrow{a}q'} cette transition.
Pour représenter graphiquement un automate, on utilise une flèche entrante pour désigner un état initial et une flèche sortante pour désigner un état final, comme l’illustre l’exemple de la figure 1.
Un mot {w=a_0\ldots a_{n-1}} est reconnu par l’automate {A} s’il existe une succession de transitions :
{\begin{array}{c}q_0\xrightarrow{a_0}q_1\xrightarrow{a_1}\ldots q_{n-1}\xrightarrow{a_{n-1}}q_n\\[8pt]\text{avec }q_0\in I\text{ et }q_n\in F.\end{array}}On dira que le mot {w} étiquette un chemin dans l’automate {A} allant de {q_0} à {q_n}.
Le langage d’un automate {A}, noté {L_A}, est exactement l’ensemble des mots reconnus par l’automate {A}. On dit alors que {A} reconnait {L_A}. Un langage est dit reconnaissable s’il est le langage d’un automate fini.
Un automate fini déterministe sur un alphabet {\Sigma} est un quadruplet {A=(Q,\{q_0\},F,\delta)}, où l’ensemble des états initiaux est un singleton (un unique état initial) et où l’ensemble des transitions {T} est remplacé par une fonction de transition {\delta} définie sur un sous-ensemble de {Q\times\Sigma} et à valeurs dans {Q}.
Pour chaque couple {(q,a)\in Q\times\Sigma}, il existe au plus une transition {(q,a,q')} qui, si elle existe, est telle que {q'=\delta(q,a)}.
L’automate est déterministe complet si la fonction de transition {\delta} est définie sur {Q\times\Sigma}. Dans ce cas, on définit la fonction de transition étendue {\delta^\star} sur {Q\times\Sigma^\star} par
{\forall q\in Q,\quad\left\{\begin{array}{l}\delta^\star(q,\varepsilon)=q\\[8pt]\delta^\star(q,wa)=\delta(\delta^\star(q,w),a)\\[8pt]\forall w\in\Sigma^\star,\ \forall a\in\Sigma.\end{array}\right.}Les automates seront représentés par le type Caml suivant
|
1 2 3 4 |
type automate = { nb : int; (* nombre d'états *) init : int list ; (* états initiaux *) final : int list; (* états finaux *) trans : (int * char * int) list} ;; (* transitions *) |
l’ensemble d’états {Q} d’un automate implémenté étant toujours supposé être un intervalle d’entiers {\llbracket0,n-1\rrbracket}.
Par exemple, l’automate {\mathcal A_1} de la figure 1 est codé par
|
1 2 3 4 |
let a1 = { nb = 3 ; init = [0]; final = [2]; trans = [(0, 'a', 0); (0, 'a', 1); (0, 'b', 0); (1, 'b', 2); (2, 'a', 2)] } ;; |
On accède au nombre d’états par a1.nb, à la liste des états initiaux par a1.init, à la liste des états finaux par a1.final et à la liste des transitions par a1.trans.
Expressions rationnelles
Soit {\Sigma} un alphabet. On définit la syntaxe des expressions rationnelles par :
— {\varnothing}, {\varepsilon} et {a} sont des expressions rationnelles, pour toute lettre {a\in\Sigma} ;
— si {E} et {F} sont deux expressions rationnelles, alors {(E+F)}, {(E\cdot F)} et {E^\star} sont des expressions rationnelles.
La sémantique des expressions rationnelles est définie par l’application {\mathcal L} qui associe à toute expression rationnelle un langage rationnel sur {\Sigma} par :
{\left\{\begin{array}{ll}\mathcal L(\varnothing)=\emptyset&\text{(langage vide)}\\[8pt]\mathcal L(\varepsilon)=\{\varepsilon\}&\text{(langage contenant le mot vide)}\\[8pt]\mathcal L(a)=\{a\}&\forall a\in\Sigma\end{array}\right.}et, si {E} et {F} sont deux expressions rationnelles,
{\left\{\begin{array}{l}\mathcal L(E+F)=\mathcal L(E)\cup\mathcal L(F)\\[8pt]\mathcal L(E\cdot F)=\mathcal L(E)\cdot\mathcal L(F)\\[8pt]\mathcal L(E^\star)=\mathcal L(E)^\star\end{array}\right.}où {\star} représente l’étoile de Kleene d’un langage et {\cdot} représente la concaténation de deux langages.
Programmation
Le seul langage de programmation autorisé dans cette épreuve est Caml.
Toutes les fonctions des modules Array et List, ainsi que les fonctions de la bibliothèque standard (celles qui s’écrivent sans nom de module, comme max ou incr ainsi que les opérateurs comme / ou mod) peuvent être librement utilisés.
Généralement, les objets mathématiques dans le texte seront notés {A,m,i,n,\ell}, alors qu’ils seront représentés en Caml par a, m, i, n, l.
Les complexités demandées sont des complexités temporelles dans le pire des cas et seront exprimées sous la forme {O(f(n,m))}, où {f} est une fonction usuelle simple et où {n} et {m} sont des paramètres correspondant aux tailles des objets en entrée de l’algorithme.
I Mots et automates
I.A – Miroir d’un mot et automate transposé
Pour tout mot {w=a_0a_1\ldots a_{n-1}} de longueur {n\in\mathbb N^\ast}, on définit son mot miroir {\widetilde w} par {\widetilde w=a_{n-1}\ldots a_1a_0}. Par convention, le mot vide {\varepsilon} est son propre miroir.
Pour tout langage {L\subset\Sigma^\star}, on définit son langage miroir {\widetilde L} constitué de l’ensemble des mots miroirs du langage {L} :
{\widetilde L=\{\widetilde w\mid w\in L\}.}
Soit {A=(Q,I,F,T)} un automate non déterministe et {L=L_A} le langage qu’il reconnait.
transpose de signature automate -> automate qui étant donné un automate {A} non déterministe en entrée, renvoie un automate non déterministe qui reconnait le miroir de {L_A}.I.B – Palindromes et rationalité
Soit {w\in\Sigma^\star}. On dit que le mot {w} est un palindrome si {\widetilde w=w}.
palindrome de signature string -> bool qui teste, en temps linéaire, si un mot est un palindrome.On rappelle que pour tout {0\le i\lt\operatorname{String.length}(s)}, le {i}-ième caractère de la chaine de caractères s est obtenu par l’expression s.[i].
Pour un alphabet {\Sigma}, on note {\operatorname{Pal}(\Sigma)} l’ensemble des palindromes de {\Sigma^\star}.
On pourra utiliser un automate et un mot de {\operatorname{Pal}(\Sigma)\cap a^\star ba^\star}.
Soit {L\subset\Sigma^\star} un langage reconnu par l’automate {A=(Q,I,F,T)}.
Pour {(q,q')\in Q^2}, on note {L_{q,q'}} le langage de tous les mots {w} qui étiquettent un chemin dans {A} partant de {q} et arrivant en {q'}.
Soit {L} un langage rationnel reconnu par un automate {A=(Q,I,F,T)}.
On définit les langages {D(L)=\{w\widetilde w\mid w\in L\}} et {R(L)=\{w\in\Sigma^\star\mid w\widetilde w\in L\}}.
On pourra faire intervenir les langages {L_{q,q'}}, définis ci-dessus.
I.C – Déterminisation
On rappelle que pour tout automate {A=(Q,I,F,T)} non déterministe, on peut définir l’automate déterminisé accessible {A_{\mathrm{det}}=(Y,\{I\},F',\delta)} où {Y\subset\mathcal P(Q)} est l’ensemble des états accessibles depuis l’état initial {\{I\}} dans l’automate des parties.
Cet automate déterminisé accessible reconnait le même langage que l’automate {A}.
Les états de {\mathcal A_3} seront renommés {e_0,e_1,\ldots}.
Ses états seront renommés {q_0,q_1,\ldots}.
On cherche à généraliser cette construction de façon effective. Pour cela, on va implémenter l’algorithme de déterminisation.
Il faut d’abord choisir une représentation pour les parties de {Q} (c’est-à-dire des ensembles d’états). Une solution naïve consisterait à utiliser des listes d’états.
Lors du déroulement de l’algorithme de déterminisation, on peut être amené à effectuer des réunions d’ensembles. Une concaténation simple des listes génère des doublons qu’il faut ensuite supprimer afin que les listes codent bien des ensembles d’états.
supprimer de signature 'a list -> 'a list qui prend une liste en entrée et supprime toutes les occurrences multiples de ses éléments.On choisit plutôt de coder les ensembles d’états par des entiers.
Pour un automate {A=(Q,I,F,T)} tel que {Q=\llbracket0,n-1\rrbracket}, toute partie de {Q} va être représentée par un entier entre {0} et {2^n-1}. Dans la suite, on supposera {n\le20}. Soit {X} une partie de {\llbracket0,n-1\rrbracket}. On définit le numéro de {X} par la fonction suivante
{\operatorname{numero}(X)=\sum_{i\in X}2^i.}On se donne pow un tableau des puissances de {2}, qui contient toutes les puissances {2^k}, pour {0\le k\le20}.
|
1 2 3 4 |
let pow = Array.make 21 1 ;; for i = 1 to 20 do pow.(i) <- pow.(i-1) * 2 done ;; |
Soit {q\in\llbracket0,n-1\rrbracket} un état et {k\in\llbracket0,2^n-1\rrbracket} le numéro d’un ensemble d’états {X}, c’est-à-dire {\operatorname{numero}(X)=k}.
est_dans de signature int -> int -> bool qui teste, à l’aide d’opérations arithmétiques, si l’état {q} est dans l’ensemble d’états représenté par le numéro {k} en {O(1)} opérations.Soit {\ell} une liste d’états contenant éventuellement plusieurs fois le même état, représentant l’ensemble {X}.
numero de signature int list -> int qui calcule le numéro de l’ensemble {X}.
Par exemple {\ell=[1;5;2;5;2;5;2;2;1;2;1]} représente l’ensemble {X=\{1,2,5\}}, de numéro {38=2^1+2^2+2^5}.
Soit {\ell} une liste d’états et {X} un ensemble d’états représenté par son numéro {k}.
intersecte de signature int list -> int -> bool qui vérifie si un élément de {\ell} est contenu dans l’ensemble {X} représenté par {k}.On prépare désormais la fonction de transition de l’automate déterminisé accessible.
Soit {X} un ensemble d’états de {Q}. On suppose désormais que l’automate est sur l’alphabet à deux lettres {\Sigma=\{a,b\}}.
On cherche à calculer la fonction de transition {\delta:\mathcal P(Q)\times\Sigma\to\mathcal P(Q)} de l’automate déterminisé. On rappelle que, pour {c\in\{a,b\}} et {X\in\mathcal P(Q)},
{\delta(X,c)=\bigcup_{q\in X}\{q'\in Q\mid(q,c,q')\in T\}.}La transition {(X,c,\delta(X,c))} sera alors dans l’automate déterminisé.
En parcourant l’ensemble des transitions {T} de l’automate, on va simultanément calculer les états {(\delta(X,a),\delta(X,b))}, ce qui correspond à la table de transition depuis l’état {X}.
etat_suivant de signature int -> (int*char*int) list -> (int*int) qui, étant donné en entrée un entier {k} tel que {k=\operatorname{numero}(X)} et la liste des transitions {T}, calcule le couple d’entiers {(k_a,k_b)} tels que {k_a=\operatorname{numero}(\delta(X,a))} et {k_b=\operatorname{numero}(\delta(X,b))}.Au moment de construire l’automate déterminisé accessible {A_{\mathrm{det}}}, on va être amené à renommer (c’est-à-dire ici renuméroter) les états de {A_{\mathrm{det}}} pour avoir au final un ensemble d’états {Y} de la forme {\llbracket0,N-1\rrbracket} où {N} sera le nombre de parties de {Q} accessibles dans l’automate des parties.
Pour cela, on va simplement utiliser une liste contenant des couples {(k,v)} où {k} est le numéro d’un ensemble d’états {X} et {v} le numéro final par lequel {k} sera remplacé.
Par exemple, si à un moment donné de l’algorithme, la liste contient {(6,2)}, « l’ensemble d’états 6 » (qui correspond dans {\mathcal P(Q)} à {\{1,2\}}) est renuméroté {2}.
cherche de signature int -> (int*int) list -> int qui renvoie le nouveau numéro d’un ensemble d’états représenté par son numéro {k} dans une liste comme ci-dessus ({-1} si {k} n’est pas présent).determinise de signature automate -> automate qui calcule le déterminisé accessible de l’automate d’entrée. On expliquera brièvement la démarche utilisée.determinise en fonction du nombre d’états {n} de {A} et du nombre d’états {N} de {A_{\mathrm{det}}} ?I.D – Algorithme de Brzozowski
L’algorithme de Brzozowski permet d’obtenir un automate déterministe ayant un nombre minimal d’états, reconnaissant le même langage que l’automate initial.
On se donne un automate {A=(Q,I,\{f\},T)} qui reconnait le langage {L} et tel que l’automate miroir {\widetilde A} est déterministe et accessible.
On note {A_{\mathrm{det}}=(Y,\{I\},F,\delta)} le déterminisé accessible de {A}.
Si {u} est un mot et {L} un langage, on note {u^{-1}L=\{w\in\Sigma^\star\mid uw\in L\}}.
minimal de signature automate -> automate appliquant la construction de Brzozowski sur l’automate d’entrée.
On fera abstraction de la taille des automates générés, possiblement problématique.
II Expression rationnelle associée à un automate
Dans cette partie, on introduit un algorithme, dû à Conway, pour le calcul de l’expression rationnelle associée au langage d’un automate, via l’utilisation de matrices dont les coefficients sont des expressions rationnelles.
II.A – Simplification d’expressions rationnelles équivalentes
On se donne en Caml le type exprat des expressions rationnelles
|
1 2 3 4 5 6 |
type exprat = Vide | Epsilon | Lettre of char | Union of exprat * exprat ;; | Concat of exprat * exprat | Etoile of exprat ;; |
II.A.1)
lettre de signature exprat -> int qui renvoie le nombre de lettres présentes dans l’expression rationnelle en argument.
Par exemple, si {E=(a^\star b)+abba(a+\varepsilon)^\star+\varnothing}, (lettre e) doit renvoyer {7}.
est_vide de signature exprat -> bool qui teste si le langage rationnel représenté par l’expression rationnelle en argument est vide.II.A.2) Dans cette section, on travaille formellement sur la syntaxe des expressions rationnelles.
On utilise les équivalences évidentes suivantes
{\begin{array}{c}\varnothing+E\equiv E+\varnothing\equiv E\\[8pt]E\cdot\varepsilon\equiv\varepsilon\cdot E\equiv E\\[8pt]E\cdot\varnothing\equiv\varnothing\cdot E\equiv\varnothing\\[8pt]\varnothing^\star\equiv\varepsilon,\quad\varepsilon^\star\equiv\varepsilon,\quad(E^\star)^\star\equiv E^\star\end{array}}où la notation {E\equiv E'} signifie que les langages représentés sont égaux : {\mathcal L(E)=\mathcal L(E')}.
La fonction suivante réalise une simplification à la racine sur une expression du type Union en suivant la règle donnée.
|
1 2 3 4 |
let su expr = match expr with | Union( Vide , e ) -> e | Union( e , Vide ) -> e | _ -> expr;; |
De même, on peut écrire une fonction sc : exprat->exprat qui simplifie à la racine une expression de type Concat. On suppose codées ces fonctions.
se : exprat -> exprat qui simplifie à la racine une expression de type Etoile avec les règles données.Prenons par exemple {E_n=(a+(b.(b.(b.(b.\ldots\varnothing)\ldots)}, où {n} lettres {b} concaténées se succèdent.
simplifie : exprat -> exprat qui simplifie une expression rationnelle selon les règles données.II.B – Matrices d’expressions rationnelles
Dans la suite, on considère des matrices d’expressions rationnelles
|
1 |
type mat = exprat array array ;; |
La matrice nulle de taille {n} est la matrice de taille {n} où chaque coefficient vaut {\varnothing}.
La matrice identité de taille {n} est la matrice de taille {n} où chaque coefficient vaut {\varepsilon} sur la diagonale et {\varnothing} en dehors de la diagonale.
On définit la somme de deux matrices {A} et {B} de taille {(n\times m)} par la matrice {A+B} de taille {(n\times m)} où {[A+B]_{i,j}=A_{i,j}+B_{i,j}} où le {+} représente l’opération rationnelle d’union et {0\le i\le n-1}, {0\le j\le m-1}.
On définit le produit de deux matrices {A} et {B} de taille {(n\times p)} et {(p\times q)} à la manière du produit matriciel usuel {AB}, de taille {(n\times q)}, où la somme de coefficients est remplacée par l’union et où le produit de coefficients est remplacé par la concaténation des expressions rationnelles.
II.B.1)
somme de signature mat -> mat -> mat effectuant la somme de deux matrices d’expressions rationnelles de même taille {(n\times p)}. Quelle est sa complexité ?produit de signature mat -> mat -> mat effectuant le produit de deux matrices d’expressions rationnelles, en supposant que les tailles sont bien compatibles (la première de taille {(n\times p)} et la seconde de taille {(p\times q)}.) On ne vérifiera pas la compatibilité des tailles.
Quelle est sa complexité ?
On cherche désormais à définir l’étoile de Kleene d’une matrice carrée d’expressions rationnelles.
II.B.2) Étude de l’étoile d’une matrice de taille 2
Plaçons-nous dans le cas d’une matrice carrée de taille {2}, {M=\begin{pmatrix}a&b\\[8pt]c&d\end{pmatrix}}, où {a,b,c} et {d} sont quatre lettres.
On associe à cette matrice {M} le graphe étiqueté à deux sommets de la figure 3.
On note {L_{i,j}} le langage de l’automate {\mathcal A_{i,j}=(\{0,1\},\{i\},\{j\},T)}, où {T=\{(i,M_{i,j},j)\mid(i,j)\in\{0,1\}^2\}}.
II.B.3) Étoile d’une matrice carrée de taille quelconque
Pour la définition de l’étoile d’une matrice carrée d’expressions rationnelles, on procède récursivement, sur la taille {n} de la matrice carrée {M} :
— si la taille vaut {1}, {M=(e)}, donc {M^\star=(e^\star)} ;
— sinon, pour {M} de taille {n\ge2}, on découpe {M} par blocs
{M=\begin{pmatrix}A&B\\[8pt]C&D\end{pmatrix}}où {A} et {D} sont carrées de taille {\ge1}, et on définit
{M^\star=\begin{pmatrix}A'&B'\\[8pt]C'&D'\end{pmatrix}}où
{\begin{array}{l}A'=(A+BD^\star C)^\star\\[8pt]B'=A^\star B(D+CA^\star B)^\star\\[8pt]C'=D^\star C(A+BD^\star C)^\star\\[8pt]D'=(D+CA^\star B)^\star\end{array}}On suppose déjà codées les deux fonctions suivantes sur les matrices d’expressions rationnelles :
— (decouper m n1 n2) renvoie quatre matrices blocs {A,B,C} et {D} telles que {A} est carrée de taille {n_1}, {D} est carrée de taille {n_2} et {M=\begin{pmatrix}A&B\\[8pt]C&D\end{pmatrix}}, où la matrice d’entrée {M} est carrée de taille {n=n_1+n_2}.
|
1 |
decouper : mat -> int -> int -> (mat*mat*mat*mat) |
— (recoller a b c d) renvoie la matrice {M=\begin{pmatrix}A&B\\[8pt]C&D\end{pmatrix}} à partir des quatre blocs {A,B,C} et {D} codés par a, b, c, d dont les tailles sont compatibles.
|
1 |
recoller : mat -> mat -> mat -> mat -> mat |
On propose la décomposition récursive suivante pour une matrice {M} carrée de taille {n\ge2},
{M=\begin{pmatrix}a&B\\[8pt]C&D\end{pmatrix}}où {a} est une lettre et {D} est carrée de taille {n-1}. Ainsi,
{M^\star=\begin{pmatrix}A'&B'\\[8pt]C'&D'\end{pmatrix}}où
{\begin{array}{l}A'=(a+BD^\star C)^\star\\[8pt]B'=a^\star B(D+Ca^\star B)^\star\\[8pt]C'=D^\star C(a+BD^\star C)^\star\\[8pt]D'=(D+Ca^\star B)^\star\end{array}}
En déduire la complexité de cet algorithme.
On se place dans le cas où la taille {n} de la matrice {M} est une puissance de {2}, avec {n\ge2}.
On propose désormais la décomposition récursive suivante
{M=\begin{pmatrix}A&B\\[8pt]C&D\end{pmatrix}}où les matrices {A} et {D} sont carrées de taille {n/2} chacune.
En déduire la complexité de cet algorithme.
Quelle complexité peut-on obtenir pour le calcul de {M^\star} ?
etoile de signature mat -> mat qui renvoie l’étoile d’une matrice en utilisant l’algorithme récursif le plus adéquat.II.C – Algorithme de Conway
Soit {A=(Q,I,F,T)} un automate, où l’ensemble d’états est {Q=\llbracket0,n-1\rrbracket}.
On définit {M_A} la matrice de transition de l’automate {A} par la matrice d’expressions rationnelles de taille {(n\times n)} telle que pour {0\le i,j\le n-1}, {[M_A]_{i,j}=\sum\limits_{c\in\Sigma\mid(i,c,j)\in T}c} s’il existe au moins une telle lettre {c}, {\varnothing} sinon.
On admet la propriété suivante : pour tout état {(i,j)\in Q^2}, {\mathcal L([M_A^\star]_{i,j})=L_{i,j}}, où {L_{i,j}} est le langage défini en question 9.
{L_A=\mathcal L([XM_A^\star Y]_{0,0})}où {X} est une matrice ligne d’expressions rationnelles de la forme {X=(x_0\ \ldots\ x_{n-1})} où chaque {x_i\in\{\varnothing,\varepsilon\}}, et {Y} est une matrice colonne d’expressions rationnelles de la forme {Y=\begin{pmatrix}y_0\\[8pt]\vdots\\[8pt]y_{n-1}\end{pmatrix}} où chaque {y_j\in\{\varnothing,\varepsilon\}}.
On précisera les valeurs de {X} et {Y} en fonction de l’automate {A}.
langage de signature automate -> exprat prenant en entrée un automate et renvoyant une expression rationnelle représentant le langage de cet automate.
Quelle est la complexité de cette fonction ?
III Automate des dérivées d’Antimirov
On propose pour conclure une méthode permettant de calculer un automate non déterministe ayant peu d’états à partir d’une expression rationnelle.
Si {S} et {S'} sont deux ensembles d’expressions rationnelles, on convient que
{S\cdot S'=\{E\cdot E'\mid(E,E')\in S\times S'\}.}En particulier, on a {\emptyset\cdot S=\emptyset} et {\{\varepsilon\}\cdot S=S}.
Soit {E} une expression rationnelle sur un alphabet {\Sigma} et soit {a\in\Sigma} une lettre. On définit la dérivée partielle de {E} par {a}, notée {\partial_a(E)}, comme un ensemble d’expressions rationnelles défini inductivement par
{\partial_a(\varnothing)=\emptyset\quad\text{(où }\emptyset\text{ est l’ensemble vide)}}{\partial_a(\varepsilon)=\emptyset}{\partial_a(b)=\left\{\begin{array}{ll}\{\varepsilon\}&\text{si }a=b\\[8pt]\emptyset&\text{sinon}\end{array}\right.\quad\text{pour toute lettre }b\in\Sigma}{\partial_a(E+F)=\partial_a(E)\cup\partial_a(F)}{\partial_a(E^\star)=\partial_a(E)\cdot\{E^\star\}}{\partial_a(EF)=\left\{\begin{array}{ll}\partial_a(E)\cdot\{F\}&\text{si }\varepsilon\notin\mathcal L(E)\\[8pt]\partial_a(E)\cdot\{F\}\cup\partial_a(F)&\text{sinon}\end{array}\right.}Notons bien que dans une dérivée partielle, on a une expression rationnelle, et que son résultat est un ensemble d’expressions rationnelles.
Par exemple, pour {E=a^\star(a+b)=(a^\star)\cdot(a+b)}, on calcule {\partial_a(E)} et {\partial_b(E)} ainsi : comme {\varepsilon\in\mathcal L(a^\star)},
{\begin{array}{rl}\partial_a(E)&=(\partial_a(a^\star))\cdot\{a+b\}\cup\partial_a(a+b)\\[8pt]&=(\partial_a a)\cdot\{a^\star\}\cdot\{a+b\}\\[8pt]&\quad\cup\partial_a(a)\cup\partial_a(b)\\[8pt]&=\{\varepsilon\}\cdot\{a^\star(a+b)\}\cup\{\varepsilon\}\cup\emptyset\\[8pt]&=\{a^\star(a+b);\varepsilon\}\end{array}}{\begin{array}{rl}\partial_b(E)&=(\partial_b(a^\star))\cdot\{a+b\}\cup\partial_b(a+b)\\[8pt]&=(\partial_b a)\cdot\{a^\star(a+b)\}\cup\emptyset\cup\{\varepsilon\}\\[8pt]&=\emptyset\cup\{\varepsilon\}\\[8pt]&=\{\varepsilon\}\end{array}}
Cette définition de dérivée partielle est étendue à tout mot {w\in\Sigma^\star} et à des ensembles d’expressions rationnelles par : pour {a\in\Sigma}, {w\in\Sigma^\star} et {S} un ensemble d’expressions rationnelles,
{\begin{array}{c}\partial_\varepsilon(E)=\{E\},\quad\partial_{wa}(E)=\partial_a(\partial_w(E)),\\[8pt]\partial_w(S)=\bigcup_{E\in S}\partial_w(E).\end{array}}On construit alors l’automate d’Antimirov à partir des dérivées partielles d’une expression rationnelle.
Partons de {E} une expression rationnelle. L’automate d’Antimirov de l’expression {E} est {A=(Q,I,F,T)} défini par
{\left\{\begin{array}{l}Q=\{E_1\mid\exists w\in\Sigma^\star,\ E_1\in\partial_w(E)\}\\[8pt]I=\{E\}\\[8pt]F=\{E_1\in Q\mid\varepsilon\in\mathcal L(E_1)\}\\[8pt]T=\{(E_1,c,E_2)\in Q\times\Sigma\times Q\\[8pt]\quad\mid E_2\in\partial_c(E_1)\}\end{array}\right.}On rappelle la notation {w^{-1}L} de la partie I : pour tout mot {w\in\Sigma^\star} et tout langage {L\subset\Sigma^\star},
{w^{-1}L=\{u\in\Sigma^\star\mid wu\in L\}.}
Pour {S} ensemble d’expressions rationnelles, on note {\mathcal L(S)} la réunion des langages des expressions de {S}. On admet que, si {E} est une expression rationnelle et {x} une lettre,
{\mathcal L(\partial_x(E))=x^{-1}\mathcal L(E).}
{\mathcal L(\partial_w(S))=w^{-1}\mathcal L(S).}
Pour tout mot {w\in\Sigma^\star} et {w\ne\varepsilon}, et pour toutes expressions rationnelles {E} et {F} sur {\Sigma}, on vérifie que
{\partial_w(E+F)=\partial_w(E)\cup\partial_w(F)\quad\text{(III.1)}}{\partial_w(EF)\subset\partial_w(E)\cdot F\cup\bigcup_{v\in S^+(w)}\partial_v(F)\quad\text{(III.2)}}{\partial_w(E^\star)\subset\bigcup_{v\in S^+(w)}\partial_v(E)\cdot E^\star\quad\text{(III.3)}}où {S^+(w)} est l’ensemble des suffixes non vides d’un mot {w}.
Pour une expression rationnelle {E}, on note
{Q(E)=\bigcup_{w\in\Sigma^\star,\ w\ne\varepsilon}\partial_w(E).}
Qu’en déduit-on sur l’automate d’Antimirov ?
FIN