Centrale Informatique optionnelle MP 2022

Option informatique
MP

4 heures Calculatrice autorisée

2022

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

On note X* l'ensemble de tous les mots formés sur l'alphabet Y.

La longueur (ou la taille) d'un mot w EUR X* est son nombre de lettres et se 
note [w|. Le mot vide, noté EUR, est le
seul mot de longueur nulle.

Si un mot w EUR X* est de longueur |w| = n, on le note w = aça;...a,_,, où les 
a, sont des lettres de YX.

Un langage sur l'alphabet Y est un ensemble L C X*.

L'étoile de Kleene d'un langage L, notée L*, est le plus petit langage qui 
inclut L, qui contient EUR et qui est
stable par concaténation.

La concaténation de deux langages L et L' est notée LL', 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 Y est un quadruplet À = 
(Q,1,F,T), où Q est un ensemble
fini d'états, I EUR Q est le sous-ensemble des états initiaux, F EUR Q est le 
sous-ensemble des états finaux et
l'ensemble T EUR Q x X x Q est l'ensemble des transitions, étiquetées par les 
lettres de l'alphabet Y.

a
Si (g,a,q') ET, on note q -- 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,...a,,_, est reconnu par l'automate À s'il existe une succession 
de transitions :
a a dn_1
do --+ di +" An-1 + An avec dEl et ga EF.
On dira que le mot w étiquette un chemin dans l'automate À allant de q à q,.

Le langage d'un automate À, noté L\, est exactement l'ensemble des mots 
reconnus par l'automate À. On dit
alors que À reconnaît L,. Un langage est dit reconnaissable s'il est le langage 
d'un automate fini.

Un automate fini déterministe sur un alphabet X est un quadruplet À = (Q, 
{},F,6), où l'ensemble des états
initiaux est un singleton (un unique état initial) et où l'ensemble des 
transitions Test remplacé par une fonction
de transition 6 définie sur un sous-ensemble de Q x Y et à valeurs dans Q. Pour 
chaque couple (q,a) E Q XX,
il existe au plus une transition (q, a, q") qui, si elle existe, est telle que 
g" = ô(q, a).

L'automate est déterministe complet si la fonction de transition 6 est définie 
sur Q x Y. Dans ce cas, on définit
la fonction de transition étendue 8* sur Q x X* par

0*(q,EUR) = q
"ae qu à Vwe>*,VaeYX

Les automates seront représentés par le type Caml suivant

type automate = { nb : int; (* nombre d'états *)
init : int list ; (x états initiaux *)
final : int list; (x états finaux *)
trans : (int * char * int) list} ;; (x transitions *)

l'ensemble d'états Q d'un automate implémenté étant toujours supposé être un 
intervalle d'entiers [0,n -- 1]|.

N007/2022-03-21 17:50:28 Page 1/9 CHELLES
&, D a

(_
OO O

Figure 1 L'automate 4,

Par exemple, l'automate 4, de la figure 1 est codé par

let ai = { nb = 3 ;
init = [O0];
final = [2];
trans = [(0, 'a', 0); (0, 'a', 1); (0, 'b', O0); (1, 'b', 2); (2, ''a', 2)] } ;;

On accède au nombre d'états par al.nb, à la liste des états initiaux par 
ai.init, à la liste des états finaux par
ai.final et à la liste des transitions par aî.trans.

Expressions rationnelles

Soit > un alphabet. On définit la syntaxe des expressions rationnelles par :

-- G,£set a sont des expressions rationnelles, pour toute lettre a EUR Y :

-- si E et F sont deux expressions rationnelles, alors (E + F), (EE: F) et E* 
sont des expressions rationnelles.

La sémantique des expressions rationnelles est définie par l'application Z qui 
associe à toute expression ration-
nelle un langage rationnel sur Y par :

£(S) =Üÿ (langage vide)
Æ(E) = {es} (langage contenant le mot vide)
£(a)= {a} VaeYr

et, si £ et F sont deux expressions rationnelles,

£L(E+F)=£(E)U£(F)
£L(E-F) = £L(E):£(F)
£(E*) = £(EY

où + représente l'étoile de Kleene d'un langage et : 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 À, m, à, n, 
EUR, alors qu'ils seront représentés
en Caml par a, m, i,n., 1.

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. À --- Miroir d'un mot et automate transposé

Pour tout mot w = apa,...a, _, de longueur n EUR N*, on définit son mot miroir 
à par & = a,_,....aa). Par
convention, le mot vide EUR est son propre miroir.

Pour tout langage L C Y*, on définit son langage miroir L constitué de 
l'ensemble des mots miroirs du langage L :

L = {&|we L}.

Q 1. Décrire le langage L, de l'automate 4, de l'exemple de la figure I et 
décrire son langage miroir L..
Q 2. Dessiner un automate À,, reconnaissant le langage miroir L..

Soit À =(Q,1,F,T) un automate non déterministe et L = L, le langage qu'il 
reconnait.

Q 3. Donner, en justifiant, la construction de l'automate miroir À = 
(Q,1",F",T") qui reconnait le langage
L.

Q 4. Écrire une fonction 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,.

Q 5. Quelle est la complexité de cette fonction ?

N007/2022-03-21 17:50:28 Page 2/9 (cc) BY-NC-SA
I.B ---  Palindromes et rationalité
Soit w EUR >. On dit que le mot w est un palindrome si & = w.

Q 6. Écrire une fonction palindrome de signature string -> bool qui teste, en 
temps linéaire, si un mot
est un palindrome.

On rappelle que pour tout 0 < à < (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 Y, on note Pal(Y) l'ensemble des palindromes de X*. Q 7. Montrer que si Y est un alphabet à une lettre, alors Pal(Y) est rationnel. Q 8. Montrer que si Y contient au moins deux lettres, alors Pal(Y) n'est pas rationnel. On pourra utiliser un automate et un mot de Pal(Y) N a*ba*. Soit L C X* un langage reconnu par l'automate À = (Q,1,F,T). Pour (q,q') EUR Q*, on note L,,.4 Xe langage de tous les mots w qui étiquettent un chemin dans À partant de q et arrivant en q'. Q 9. Montrer que L, est reconnaissable et exprimer le langage LA en fonction de langages L Q 10. Montrer que Pal(E) N (52) = {uü | u EUR X*}. Soit L un langage rationnel reconnu par un automate À = (Q,1,F,T). On définit les langages D(L) = {ww | w EUR L} et R(L) = {w EUR X* | ww EUR L}. Q 11. Décrire simplement les langages D(a*b) et R(a*b*a*). Q 12. Les langages D(L) et R(L) sont-ils reconnaissables ? On pourra faire intervenir les langages L q,q'° qq'? définis ci-dessus. IC -- Déterminisation On rappelle que pour tout automate À = (Q,1,F,T) non déterministe, on peut définir l'automate déterminisé accessible A+ = (Y,{1},F",6) où Y C P(Q) est l'ensemble des états accessibles depuis l'état initial {7} dans l'automate des parties. Cet automate déterminisé accessible reconnait le même langage que l'automate À. Q 13. Écrire un automate 4, non déterministe à 4 états qui reconnait le langage L, = (b + ab)*ba. Cet automate devra avoir un unique état initial et un unique état final. Q 14. Appliquer l'algorithme de déterminisation sur l'automate miroir A, afin d'obtenir l'automate 4, = (A) . Les états de .4, seront renommés EUR,,e],.... det Q 15. Appliquer l'algorithme de déterminisation sur l'automate miroir A, afin d'obtenir l'automate .4, -- (A3). _ Ses états seront renommés Gp, 4: EUR Q 16. Quel doit être le langage reconnu par l'automate 4, ? On cherche à généraliser cette construction de façon effective. Pour cela, on va implémenter l'algorithme de déterminisation. H 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. Q 17. Écrire une fonction supprimer de signature 'a list -> 'a list qui prend 
une liste en entrée et
supprime toutes les occurrences multiples de ses éléments.

Q 18. Donner la complexité de votre algorithme en fonction de la taille de la 
liste d'entrée.
On choisit plutôt de coder les ensembles d'états par des entiers.

Pour un automate À = (Q,1,F,T) tel que Q = [0,n -- 1] , toute partie de Q va 
être représentée par un entier
entre 0 et 2° -- 1. Dans la suite, on supposera n < 20. Soit X une partie de [0,n -- 1]. On définit le numéro de X par la fonction suivante numero(X) -- > 2?.

iEX
On se donne pow un tableau des puissances de 2, qui contient toutes les 
puissances 2, pour 0 < k < 20. let pow = Array.make 21 1 ;; for i = 1 to 20 do pow.(i) <- pow.(i-1) * 2 done ;; Soit q EUR [0,n -- 1] un état et k EUR ]0, 2" -- 1] le numéro d'un ensemble d'états X, c'est-à-dire numero(X) = k. N007/2022-03-21 17:50:28 Page 3/9 (cc) BY-NC-SA Q 19. Écrire une fonction est_dans de signature int -> int -> bool qui teste, à 
l'aide d'opérations arith-
métiques, si l'état q est dans l'ensemble d'états représenté par le numéro k en 
O(1) opérations.

Soit £ une liste d'états contenant éventuellement plusieurs fois le même état, 
représentant l'ensemble X.

Q 20. Écrire une fonction numero de signature int list -> int qui calcule le 
numéro de l'ensemble X.
Par exemple £ = [1; 5; 2; 5; 2; 5; 2; 2; 1; 2; 1] représente l'ensemble X = 
{1,2,5}, de numéro 38 = 21 + 22 +2.
Soit £ une liste d'états et À un ensemble d'états représenté par son numéro k.

Q 21. Écrire une fonction intersecte de signature int list -> int -> bool qui 
vérifie si un élément de
£ 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 À un ensemble d'états de Q. On suppose désormais que l'automate est sur 
l'alphabet à deux lettres
Z = {a,b}.

On cherche à calculer la fonction de transition 8 : P(Q) x Y -- P(Q) de 
l'automate déterminisé. On rappelle
que, pour c EUR {a,b} et X EUR P(Q),

(X,c)= | J{a EQl(acd)eT}.

ge X

La transition (X,c,ô(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 (Ô(X, a), Ô(X,b)),
ce qui correspond à la table de transition depuis l'état X.

Q 22. Écrire une fonction etat_suivant de signature int -> (int*char*int) list 
-> (int*int) qui.
étant donné en entrée un entier k tel que k = numero(X) et la liste des 
transitions T, calcule le couple d'entiers
(k,.k,) tels que k, = numero(ô(X, a)) et k, = numero(ô(X,b)).

Au moment de construire l'automate déterminisé accessible A... on va être amené 
à renommer (c'est-à-dire ici
renuméroter) les états de A4. pour avoir au final un ensemble d'états Y de la 
forme [0, N -- 1] 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 P(Q) à {1,2}) est renuméroté 2.

Q 23. Écrire une fonction 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).

Q 24. Écrire une fonction determinise de signature automate -> automate qui 
calcule le déterminisé ac-
cessible de l'automate d'entrée. On expliquera brièvement la démarche utilisée.

Q 25. Quelle est la complexité de votre fonction determinise en fonction du 
nombre d'états n de À et du
nombre d'états N de À, ?

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 À = (Q,1,{f},T) qui reconnait le langage L et tel que 
l'automate miroir À est
déterministe et accessible.

On note A4, = (Y,{1},F,6) le déterminisé accessible de À.

Si u est un mot et L un langage, on note u !L = {w EUR X* | uw EUR LÀ}.

Q 26. Soit q EUR Q un état et u EUR X* un mot. Montrer que si q EUR 0*({1},u), 
alors il existe un mot w EUR Y* tel
que uw EUR L.

Q 27. Montrer la propriété (+) : si l'on prend deux mots u et v dans X* tels 
que u ÎL = vw IL, alors dans
l'automate À. déterminisé, 0*({1},u) = 0*({1},u).

Q 28. En déduire que si À est un automate quelconque reconnaissant L, alors en 
posant B -- (A). , montrer
et

que (B).. reconnait L et vérifie la propriété (+).

Q 29. Écrire une fonction minimal de signature automate -> automate appliquant 
la construction de Br-
zozowski sur l'automate d'entrée. On fera abstraction de la taille des 
automates générés, possiblement problé-
matique.

N007/2022-03-21 17:50:28 Page 4/9 (cc) BY-NC-SA
IT 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.

IT. À -- Simplification d'expressions rationnelles équivalentes

On se donne en Caml le type exprat des expressions rationnelles

Vide
Epsilon

type exprat -
|
| Lettre of char
|
|
|

Union of exprat * exprat ;;
Concat of exprat * exprat
Etoile of exprat ;;

II.A.1)

Q 30. Écrire une fonction lettre de signature exprat -> int qui renvoie le 
nombre de lettres présentes
dans l'expression rationnelle en argument. Par exemple, si E = (a*b) + abba(a + 
EUR) + @, (lettre e) doit
renvoyer 7.

Q 31. Écrire une fonction 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
G+E=E+SG=E E-e=c. E=E E-G=g'E=g D'=E ZE (EX) = E*

où la notation E = FE" signifie que les langages représentés sont égaux : £(E) 
= £(E).
La fonction suivante réalise une simplification à la racine sur une expression 
du type Union en suivant la règle
donnée.

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.

Q 32. Écrire une fonction se : exprat -> exprat qui simplifie à la racine une 
expression de type Etoile
avec les règles données.

Prenons par exemple Æ,, = (a + (b.(b.(b.(b....@)...), où n lettres b 
concaténées se succèdent.
> TK
' TT Le

ur SC

, TN

To

Figure 2 Exemple de l'arbre syntaxique de
l'expression E,

b

Q 33. Combien d'applications de règles décrites ci-dessus sont-elles 
nécessaires pour obtenir à partir de E,,
l'expression équivalente a ?

Q 34. Écrire une fonction 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
type mat - exprat array array ;;

La matrice nulle de taille n est la matrice de taille n où chaque coefficient 
vaut G.

N007/2022-03-21 17:50:28 Page 5/9 (cc) BY-NC-SA
La matrice identité de taille n est la matrice de taille n où chaque 
coefficient vaut EUR sur la diagonale et g en
dehors de la diagonale.

On définit la somme de deux matrices À et B de taille (n X m) par la matrice À 
+ B de taille (n X m) où
A+B|,,;= A;,+8B,;; où le + représente l'opération rationnelle d'union et 0 
 mat -> mat effectuant la 
somme de deux matrices
d'expressions rationnelles de même taille (n X p). Quelle est sa complexité ?

Q 36. Écrire une fonction 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 x p) et la
seconde de taille (p x 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

Placons-nous dans le cas d'une matrice carrée de taille 2, M -- fe 1) où à, b, 
cet d sont quatre lettres.

On associe à cette matrice M le graphe étiqueté à deux sommets de la figure 3.

a d

(+ br (C;

Figure 3
On note L, ; le langage de l'automate 4,,; = ({0,1},{i}, {5}, T), où T = {{(i, 
M,,,j) | (à,j) EUR {0,1}°}.
Q 37. Donner une expression rationnelle sur l'alphabet {a, b,c,d} pour décrire 
chaque langage L;;.

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* = (e*) ;

-- sinon, pour M de taille n > 2, on découpe M par blocs
M = (é
où À et D sont carrées de taille > 1, et on définit

ke A' B'
mé»)

a
G &
Se

A'=(A+BD*C)  B'=A*B(D+CA*B*  C'=D*C(A+BD*CY*  D'=(D+CA'B)

On suppose déjà codées les deux fonctions suivantes sur les matrices 
d'expressions rationnelles :

-- (decouper m ni n2) renvoie quatre matrices blocs À, B, Cet D telles que À 
est carrée de taille n,, D est
A

carrée de taille n, et M -- | C D) où la matrice d'entrée M est carrée de 
taille n = n; + no.

decouper : mat -> int -> int -> (mat*mat*mat*mat)

o n) à partir des quatre blocs À, B, Cet D codés par

-- (recoller a b c d) renvoie la matrice M -- |

a, b, c, d dont les tailles sont compatibles.

recoller : mat -> mat -> mat -> mat -> mat

N007/2022-03-21 17:50:28 Page 6/9 (cc) BY-NC-SA
On propose la décomposition récursive suivante pour une matrice M carrée de 
taille n > 2,
a BD
M --
où a est une lettre et D est carrée de taille n -- 1. Aïnsi.

ke A/ B'
mé»)

A'=(a+BD*C* B'=&@B(D+Ca*B*  C'=D*C(a+BD*C*  D'=(D+CaB)

Q 38. Évaluer les différentes complexités des sommes et produits effectués, et 
en déduire que si C{(n) est la
complexité du calcul de l'étoile pour une matrice de taille n, alors C(n) = 
2C(n -- 1) + O(n*). 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 2 2.

On propose désormais la décomposition récursive suivante
A B
M --
où les matrices À et D sont carrées de taille n/2 chacune.

Q 39. Évaluer les différentes complexités des sommes et produits effectués, et 
en déduire que si C(n) est
la complexité du calcul de l'étoile pour une matrice de taille n, alors C{n) = 
4C(n/2) + O(n*). En déduire la
complexité de cet algorithme.

Q 40. Comment gérer le cas des matrices M de taille n quelconque ? Quelle 
complexité peut-on obtenir pour
le calcul de M ?

Q 41. Écrire la fonction etoile de signature mat -> mat qui renvoie l'étoile 
d'une matrice en utilisant
l'algorithme récursif le plus adéquat.

ITI.C -- Algorithme de Conway

Soit À = (Q,1,F,T) un automate, où l'ensemble d'états est Q = [0,n -- 11].

On définit M, la matrice de transition de l'automate À par la matrice 
d'expressions rationnelles de taille (n x n)

telle que pour 0  c s'il existe au moins une telle 
lettre c, @ sinon.
ceYl(i,c,j)eT

On admet la propriété suivante : pour tout état (4, j) EUR Q*, L(IM°;,) = L;,, 
où L;,; est le langage défini en

question 9.

Q 42. Montrer que

LA -- £(IX M Ylo0.0)

où X est une matrice ligne d'expressions rationnelles de la forme X = (x, + 
x,_.) où chaque x, EUR {@,e},

et Y est une matrice colonne d'expressions rationnelles de la forme Y -- " où 
chaque y; EUR {9,EUR}. On
Un--1

précisera les valeurs de X et Y en fonction de l'automate À.

Q 43. Écrire la fonction langage de signature automate -> exprat prenant en 
entrée un automate et ren-

voyant une expression rationnelle représentant le langage de cet automate. 
Quelle est la complexité de cette

fonction ?

N007/2022-03-21 17:50:28 Page 7/9 (cc) BY-NC-SA
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-S"={E.-E|(E, F)EeS x S"}
En particulier, on aÜ:S--=fet {e}-S =S.

Soit Æ une expression rationnelle sur un alphabet Y et soit a EUR Y une lettre. 
On définit la dérivée partielle de
E par a, notée 0,(Æ), comme un ensemble d'expressions rationnelles défini 
inductivement par

(où ( est l'ensemble vide)

pour toute lettre b EUR Y

nue (E).{F} sie L(E)
)-{F}UO,(F) sinon

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*(a +b) = (a*) : (a +b), on calcule 0,(E) et O,(E) ainsi 
: comme EUR EUR £(a*),
(0, (a*)) : {a+ b}UO,(a +b)
= (d, ï {a}: {a+b}U0, (a) U0,(b)
{e}: {a*(a+b)}U{e} UV

LT (a+b);e}
= (0,(a*)) - {a + b} U 0,(a +b)
-- (04,4) : {a*(a+b)}UÜU {e}
= DU

Q 44. Pour E = (ab + b)*ba, calculer 0,(Æ) et 0,(E).

Cette définition de dérivée partielle est étendue à tout mot w EUR X* et à des 
ensembles d'expressions rationnelles
par: pou a EUR », we > et S un ensemble d'expressions rationnelles,

O.(E) = {E} Oya(E) = 0,(0(E)) d,(5) = (] 8,(E
FEES
On construit alors l'automate d'Antimirov à partir des dérivées partielles 
d'une expression rationnelle.

Partons de Æ une expression rationnelle. L'automate d'Antimirov de l'expression 
Æ est À = (Q,1,F,T) défini
par

Q={E, |2wED*,E, EO,(E)}

1={E}

F={E eQ|ee£L(E,;)}
T={(E,cE)EeQxExQ IE, EUR d(E)]

On rappelle la notation w !L de la partie I: pour tout mot w EUR X* et tout 
langage L EUR Y*,
w iL={ueX* | wuEe L}

Q 45. Dessiner l'automate obtenu à partir de l'expression rationnelle Æ = (ab + 
b)*ba. On indiquera précisé-
ment l'ensemble d'états Q.

Q 46. Montrer que pour tous mots u, v et tout langage L, v Tu ÎL = (uv) EL.

Pour $S ensemble d'expressions rationnelles, on note £(S) la réunion des 
langages des expressions de S$. On
admet que, si Æ est une expression rationnelle et x une lettre,

L(D,(E)) = x" £(E)

N007/2022-03-21 17:50:28 Page 8/9 (cc) BY-NC-SA
Q 47. Soit S un ensemble d'expressions rationnelles sur Y et w un mot de >*. 
Montrer que
L(O,,(5)) = w1£(S).

Q 48. Montrer que pour tout mot w EUR X*, l'ensemble 0,,(E) est l'ensemble des 
états accessibles depuis l'état
FE en lisant le mot w.
Q 49. En déduire que l'automate d'Antimirov reconnait bien le langage de 
l'expression rationnelle E,.

Pour tout mot w EUR X* et w £ EUR, et pour toutes expressions rationnelles Æ et 
F sur Y, on vérifie que

d,(E+F)=0,(E)UO, (F) (IIL.1)
DEF) CO(E)-FU |] à,(F) (IIL.2)
vEST(w)
0,(E)EUR |] à,(E)-E* (IIL.3)
vEST(w)

où S'(w) est l'ensemble des suffixes non vides d'un mot w.
Pour une expression rationnelle Æ, on note

Q(E)= |) ,(E).

WEDÏ*, WE

Q 50. Montrer que pour toute expression rationnelle Æ, le cardinal de Q(E) est 
majoré par le nombre de
lettres présentes dans l'écriture syntaxique de Æ (qu'on notera |E|). Qu'en 
déduit-on sur l'automate d'Antimi-
rov ?

eeoeFrINeee

Page 9/9 CITES

N007/2022-03-21 17:50:28