WikiPrépaLivrets

Centrale Option Informatique MP 2022Sujet et rapport du jury

Pas encore noté
  • Langages, mots et automates finis
  • Expressions rationnelles
  • Algorithmes diviser pour régner et complexité
  • Programmation en OCaml
Logo concours Centrale

Explorer les annales

BanqueCentraleAnnée2022FilièreMPMatièreInformatique
Annales Centrale MP InformatiqueCentrale MP 2022MP InformatiqueInformatique 2022

Téléchargements

Télécharger le sujet (PDF)
Rapport du juryLire en ligneLaTeXWord
  • Corrigé : pas encore disponible

Présentation du sujet

Difficile
Automates, expressions rationnelles et algorithmes associés
Afficher ou masquer la section

Le sujet porte sur des algorithmes classiques liant automates et expressions rationnelles, en trois parties indépendantes. La première étudie le miroir d'un langage puis implémente la déterminisation d'un automate jusqu'à l'algorithme de Brzozowski. La deuxième programme une représentation OCaml des expressions rationnelles et l'algorithme dichotomique de Conway. La troisième introduit les dérivées d'Antimirov pour construire un automate associé à une expression rationnelle.

  1. 1I - Mots et automatesMiroir d'un mot et automate transposé, palindromes et rationalité, déterminisation d'un automate, algorithme de Brzozowski.
  2. 2II - Expression rationnelle associée à un automateSimplification d'expressions rationnelles, matrices d'expressions rationnelles et algorithme de Conway pour calculer une expression rationnelle du langage d'un automate.
  3. 3III - Automate des dérivées d'AntimirovConstruction d'un automate associé à une expression rationnelle à partir de ses dérivées, avec preuve de correction et borne sur le nombre d'états.

Difficile. Le jury note que le sujet portait sur une partie difficile du programme et que la troisième partie, plus courte mais plus difficile, n'a été abordée sérieusement que dans les meilleures copies.

L'épreuve en chiffres

Moyenne 9,45 / 20 · écart-type 4,02 · 1 689 présents · où vous situez-vous ?
Afficher ou masquer la section
Moyenne
9,45/ 20
Écart-type
4,02
Présents
1 689
Coefficient
10
Durée
4 h
1er quartile
6,4
Médiane
9,3
3e quartile
12,4
moyenne 9,4505101520
Deux tiers des copies environ (moyenne ± écart-type)

Votre note sur 20 à ce sujet, en conditions de concours.

Source : document officiel du concours, épreuve du 4 mai 2022. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

5 erreurs relevées
Oubli systématique des parenthèses en OCaml · Confusions entre OCaml et Python · Confusion entre caractère et variable
Afficher ou masquer la section

Le sujet comportait à parts à peu près égales des questions de programmation et des questions théoriques sur les langages et les automates. La partie programmation est dans l'ensemble plutôt réussie, avec une bonne maîtrise des bases d'OCaml, tandis que les réponses aux questions théoriques ont été plus souvent confuses ou sans véritable justification.

Les erreurs les plus sanctionnées

  1. 1
    Oubli systématique des parenthèses en OCaml

    L'oubli quasi-systématique des parenthèses dans le passage des paramètres à une fonction, ou des délimiteurs begin/end, provoque des erreurs de comportement du programme.

    « l'oubli quasi-systématique des parenthèses dans le passage des paramètres à une fonction »
  2. 2
    Confusions entre OCaml et Python

    Le jury rencontre encore trop souvent des confusions avec Python sur la manipulation des listes ou les bornes dans les boucles for.

    « on rencontre encore trop souvent des confusions avec Python sur la manipulation des listes »
  3. 3
    Confusion entre caractère et variable

    Les candidats confondent le caractère 'a' de type char avec une variable nommée a.

    « confusion entre le caractère'a' de type »
  4. 4
    Simplification récursive incomplète des expressions rationnellesQ34

    La question Q34, qui demandait de simplifier récursivement en profondeur une expression rationnelle, est souvent mal traitée : trop de candidats se limitent à tester une simplification à la racine, produisant parfois des boucles infinies.

    « La question Q34 est souvent mal traitée »
  5. 5
    Optimisation de la représentation des ensembles d'états non compriseQ20, Q22, Q24

    De nombreux candidats n'ont pas compris qu'il fallait travailler directement avec la représentation binaire des ensembles d'états proposée par le sujet, annulant ainsi l'optimisation attendue.

    « De nombreux candidats n'ont pas compris la démarche »

Ce qui a été bien réussi

  • La partie programmation est dans l'ensemble plutôt réussie avec une bonne maîtrise des bases du langage OCaml sur la plupart des copies.
  • Les questions de la partie II.C et de la partie III, quand elles ont été abordées sérieusement, ont été dans l'ensemble plutôt bien traitées.
  • Le jury a noté cette année une amélioration certaine dans la présentation des copies.

Conseils du jury

  • Bien lire chaque partie dans sa totalité pour en comprendre l'esprit avant de commencer à répondre, en particulier lorsque le sujet propose une implémentation optimisée à utiliser.
  • Ne pas hésiter à utiliser les fonctions basiques des modules List ou Array plutôt que de les reprogrammer, en connaissant leur complexité.
  • Gérer le temps en tenant compte de l'indépendance des parties, pour ne pas se priver des points abordables d'une partie suivante.
  • S'imposer un entraînement régulier sur machine et s'habituer à rédiger en détail les questions théoriques.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

Option informatique

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 Σ.
On note Σ^⋆ l'ensemble de tous les mots formés sur l'alphabet Σ.
La longueur (ou la taille) d'un mot w ∈ Σ^⋆ est son nombre de lettres et se note |w|. Le mot vide, noté ε, est le seul mot de longueur nulle.
Si un mot w ∈ Σ^⋆ est de longueur |w| = n, on le note w = a_0 a_1…a_(n − 1), où les a_i sont des lettres de Σ.
Un langage sur l'alphabet Σ est un ensemble L ⊂ Σ^⋆.
L'étoile de Kleene d'un langage L, notée L^⋆, est le plus petit langage qui inclut L, qui contient ε et qui est stable par concaténation.
La concaténation de deux langages L et L^′ est notée L ⋅ 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 Σ est un quadruplet A = (Q, I, F, T), où Q est un ensemble fini d'états, I ⊂ Q est le sous-ensemble des états initiaux, F ⊂ Q est le sous-ensemble des états finaux et l'ensemble T ⊂ Q × Σ × Q est l'ensemble des transitions, étiquetées par les lettres de l'alphabet Σ.
Si (q, a, q^′) ∈ T, on note q → ^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…a_(n − 1) est reconnu par l'automate A s'il existe une succession de transitions:
q_0→−^(a_0)q_1→−^(a_1)⋯q_(n − 1)→−^(a_(n − 1))q_n avec q_0 ∈ I et q_n ∈ F.
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 Σ est un quadruplet A = (Q, {q_0}, F, δ), 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 δ définie sur un sous-ensemble de Q × Σ et à valeurs dans Q. Pour chaque couple (q, a) ∈ Q × Σ, il existe au plus une transition ( q, a, q^′ ) qui, si elle existe, est telle que q^′ = δ(q, a).
L'automate est déterministe complet si la fonction de transition δ est définie sur Q × Σ. Dans ce cas, on définit la fonction de transition étendue δ^⋆ sur Q × Σ^⋆ par
∀q ∈ Q, {δ^⋆(q, ε) = q; δ^⋆(q, wa) = δ(δ^⋆(q, w), a) ∀w ∈ Σ^⋆, ∀a ∈ Σ
Les automates seront représentés par le type Caml suivant
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 [ [0, n − 1] ].
Figure 1 L'automate A_1
Par exemple, l'automate A_1 de la figure 1 est codé par
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 Σ un alphabet. On définit la syntaxe des expressions rationnelles par:
  • ∅, ε et a sont des expressions rationnelles, pour toute lettre a ∈ Σ;
  • si E et F sont deux expressions rationnelles, alors (E + F), (E ⋅ F) et E^⋆ sont des expressions rationnelles.
La sémantique des expressions rationnelles est définie par l'application L qui associe à toute expression rationnelle un langage rationnel sur Σ par:
{L(∅) = ∅, (langage vide); L(ε) = {ε}, (langage contenant le mot vide); L(a) = {a}, ∀a ∈ Σ
et, si E et F sont deux expressions rationnelles,
{L(E + F) = L(E) ∪ L(F); L(E ⋅ F) = L(E) ⋅ L(F); L(E^⋆) = L(E)^⋆
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 A, m, i, n, ℓ, 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_0 a_1…a_(n − 1) de longueur n ∈ ℕ^∗, on définit son mot miroir w~ par w~ = a_(n − 1)…a_1 a_0. Par convention, le mot vide ε est son propre miroir.
Pour tout langage L ⊂ Σ^⋆, on définit son langage miroir L~ constitué de l'ensemble des mots miroirs du langage L :
L~ = {w~|w ∈ L}.
Q 1. Décrire le langage L_1 de l'automate A_1 de l'exemple de la figure 1 et décrire son langage miroir L~_1.
Q 2. Dessiner un automate A~_1, reconnaissant le langage miroir L~_1.
Soit A = (Q, I, F, T) un automate non déterministe et L = L_A le langage qu'il reconnait.
Q 3. Donner, en justifiant, la construction de l'automate miroir A~ = (Q, I^′, 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_A.
Q 5. Quelle est la complexité de cette fonction ?

I.B - Palindromes et rationalité

Soit w ∈ Σ^⋆. On dit que le mot w est un palindrome si w~ = 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 ⩽ i < (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 Σ, on note Pal(Σ) l'ensemble des palindromes de Σ^⋆.
Q 7. Montrer que si Σ est un alphabet à une lettre, alors Pal(Σ) est rationnel.
Q 8. Montrer que si Σ contient au moins deux lettres, alors Pal(Σ) n'est pas rationnel.
On pourra utiliser un automate et un mot de Pal(Σ) ∩ a^⋆ba^⋆.
Soit L ⊂ Σ^⋆ un langage reconnu par l'automate A = (Q, I, F, T).
Pour (q, q^′) ∈ 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^′.
Q 9. Montrer que L_(q, q^′) est reconnaissable et exprimer le langage L_A en fonction de langages L_(q, q^′).
Q 10. Montrer que Pal(Σ) ∩ (Σ^2)^⋆ = {uu~|u ∈ Σ^⋆}.
Soit L un langage rationnel reconnu par un automate A = (Q, I, F, T).
On définit les langages D(L) = {ww~|w ∈ L} et R(L) = {w ∈ Σ^⋆|ww~ ∈ 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^′), 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_(det) = (Y, {I}, F^′, δ) où Y ⊂ 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.
Q 13. Écrire un automate A_2 non déterministe à 4 états qui reconnait le langage L_2 = (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_2˜ afin d'obtenir l'automate A_3 = (A_2˜)_(det). Les états de A_3 seront renommés e_0, e_1, ….
Q 15. Appliquer l'algorithme de déterminisation sur l'automate miroir A_3˜ afin d'obtenir l'automate A_4 = (A_3˜)_(det). Ses états seront renommés q_0, q_1, …
Q 16. Quel doit être le langage reconnu par l'automate A_4 ?
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.
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 A = (Q, I, F, T) tel que Q = [ [0, n − 1] ], toute partie de Q va être représentée par un entier entre 0 et 2^n − 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) = ∑_(i ∈ X)2^i
On se donne pow un tableau des puissances de 2 , qui contient toutes les puissances 2^k, 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 ∈ [ [0, n − 1] ] un état et k ∈ [ [0, 2^n − 1] ] le numéro d'un ensemble d'états X, c'est-à-dire numero (X) = k.
Q 19. Écrire une fonction 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 ℓ 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 = 2^1 + 2^2 + 2^5.
Soit ℓ une liste d'états et X 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 X un ensemble d'états de Q. On suppose désormais que l'automate est sur l'alphabet à deux lettres Σ = {a, b}.
On cherche à calculer la fonction de transition δ : P(Q) × Σ → P(Q) de l'automate déterminisé. On rappelle que, pour c ∈ {a, b} et X ∈ P(Q),
δ(X, c) = ⋃_(q ∈ X){q^′ ∈ Q|(q, c, q^′) ∈ T}
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 → (intcharint) list → (intint) 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_a, k_b ) tels que k_a = numero(δ(X, a)) et k_b = numero(δ(X, b)).
Au moment de construire l'automate déterminisé accessible A_(det), on va être amené à renommer (c'est-à-dire ici renuméroter) les états de A_(det) 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 → (intint) 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é accessible 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 A et du nombre d'états N de A_(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 A~ est déterministe et accessible.
On note A_(det) = (Y, {I}, F, δ) le déterminisé accessible de A.
Si u est un mot et L un langage, on note u^(− 1)L = {w ∈ Σ^⋆|uw ∈ L}.
Q 26. Soit q ∈ Q un état et u ∈ Σ^⋆ un mot. Montrer que si q ∈ δ^⋆({I}, u), alors il existe un mot w ∈ Σ^⋆ tel que uw ∈ L.
Q 27. Montrer la propriété () : si l'on prend deux mots u et v dans Σ^⋆ tels que u^(− 1)L = v^(− 1)L, alors dans l'automate A_(det) déterminisé, δ^⋆({I}, u) = δ^⋆({I}, v).
Q 28. En déduire que si A est un automate quelconque reconnaissant L, alors en posant B = (A~)_(det), montrer que (B~)_(det) 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.

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
type exprat = Vide
    | Epsilon
    | 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 + ε)^⋆ + ∅, (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
∅ + E ≡ E + ∅ ≡ E E ⋅ ε ≡ ε ⋅ E ≡ E E ⋅ ∅ ≡ ∅ ⋅ E ≡ ∅ ∅^⋆ ≡ ε ε^⋆ ≡ ε (E^⋆)^⋆ ≡ E^⋆
où la notation E ≡ E^′ signifie que les langages représentés sont égaux : L(E) = L(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 E_n = (a + (b.(b.(b.(b….∅)…), où n lettres b concaténées se succèdent.
Figure 2 Exemple de l'arbre syntaxique de l'expression E_4
Q 33. Combien d'applications de règles décrites ci-dessus sont-elles nécessaires pour obtenir à partir de E_n 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 ∅.
La matrice identité de taille n est la matrice de taille n où chaque coefficient vaut ε sur la diagonale et ∅ en dehors de la diagonale.
On définit la somme de deux matrices A et B de taille ( n × m ) par la matrice A + B de taille ( n × m ) où [A + B]_(i, j) = A_(i, j) + B_(i, j) où le + représente l'opération rationnelle d'union et 0 ⩽ i ⩽ n − 1, 0 ⩽ j ⩽ m − 1.
On définit le produit de deux matrices A et B de taille (n × p) et (p × q) à la manière du produit matriciel usuel AB, de taille ( n × 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)

Q 35. Écrire une fonction somme de signature mat → mat → mat effectuant la somme de deux matrices d'expressions rationnelles de même taille ( n × 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 × p ) et la seconde de taille (p × 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 = (a, b; c, d), où a, b, c et d sont quatre lettres.
On associe à cette matrice M le graphe étiqueté à deux sommets de la figure 3 .
Figure 3
On note L_(i, j) le langage de l'automate A_(i, j) = ({0, 1}, {i}, {j}, T), où T = {(i, M_(i, j), j)|(i, j) ∈ {0, 1}^2}.
Q 37. Donner une expression rationnelle sur l'alphabet {a, b, c, d} pour décrire chaque langage L_(i, j).

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 = (A, B; C, D)
où A et D sont carrées de taille ⩾ 1, et on définit
M^⋆ = (A^′, B^′; C^′, D^′)
où
A^′ = (A + BD^⋆C)^⋆ B^′ = A^⋆B(D + CA^⋆B)^⋆ C^′ = D^⋆C(A + BD^⋆C)^⋆ D^′ = (D + CA^⋆B)^⋆
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 = (A, B; C, D), où la matrice d'entrée M est carrée de taille n = n_1 + n_2.
decouper : mat -> int -> int -> (mat*mat*mat*mat)
  • (recoller a b c d) renvoie la matrice M = (A, B; C, D) à partir des quatre blocs A, B, C et D codés par a, b, c, d dont les tailles sont compatibles.
recoller : mat -> mat -> mat -> mat -> mat
On propose la décomposition récursive suivante pour une matrice M carrée de taille n ⩾ 2,
M = (a, B; C, D)
où a est une lettre et D est carrée de taille n − 1. Ainsi,
M^⋆ = (A^′, B^′; C^′, D^′)
où
A^′ = (a + BD^⋆C)^⋆ B^′ = a^⋆B(D + Ca^⋆B)^⋆ C^′ = D^⋆C(a + BD^⋆C)^⋆ D^′ = (D + Ca^⋆B)^⋆
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^2). 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.
On propose désormais la décomposition récursive suivante
M = (A, B; C, D)
où les matrices A 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^3). 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.

II.C - Algorithme de Conway

Soit A = (Q, I, F, T) un automate, où l'ensemble d'états est Q = [ [0, n − 1] ].
On définit M_A la matrice de transition de l'automate A par la matrice d'expressions rationnelles de taille ( n × n ) telle que pour 0 ⩽ i, j ⩽ n − 1, [M_A]_(i, j) = ∑_(c ∈ Σ|(i, c, j) ∈ T)c s'il existe au moins une telle lettre c, ∅ sinon.
On admet la propriété suivante : pour tout état (i, j) ∈ Q^2, L([M_A^⋆]_(i, j)) = L_(i, j), où L_(i, j) est le langage défini en question 9.
Q 42. Montrer que
L_A = L([XM_A^⋆Y]_(0, 0))
où X est une matrice ligne d'expressions rationnelles de la forme X = (x_0, ⋯, x_(n − 1)) où chaque x_i ∈ {∅, ε}, et Y est une matrice colonne d'expressions rationnelles de la forme Y = (y_0; ⋮; y_(n − 1)) où chaque y_j ∈ {∅, ε}. On précisera les valeurs de X et Y en fonction de l'automate A.
Q 43. Écrire la fonction 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 ⋅ S^′ = {E ⋅ E^′|(E, E^′) ∈ S × S^′}
En particulier, on a ∅ ⋅ S = ∅ et {ε} ⋅ S = S.
Soit E une expression rationnelle sur un alphabet Σ et soit a ∈ Σ une lettre. On définit la dérivée partielle de E par a, notée ∂_a(E), comme un ensemble d'expressions rationnelles défini inductivement par
∂_a(∅), = ∅, (où ∅ est l'ensemble vide); ∂_a(ε), = ∅; ∂_a(b), = {{ε}, si a = b; ∅, sinon; ∂_a(E + F), = ∂_a(E) ∪ ∂_a(F); ∂_a(E^⋆), = ∂_a(E) ⋅ {E^⋆}; ∂_a(EF), = {∂_a(E) ⋅ {F}, si ε ∉ L(E); ∂_a(E) ⋅ {F} ∪ ∂_a(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 ∂_a(E) et ∂_b(E) ainsi : comme ε ∈ L(a^⋆),
∂_a(E), = (∂_a(a^⋆)) ⋅ {a + b} ∪ ∂_a(a + b); = (∂_a a) ⋅ {a^⋆} ⋅ {a + b} ∪ ∂_a(a) ∪ ∂_a(b); = {ε} ⋅ {a^⋆(a + b)} ∪ {ε} ∪ ∅; = {a^⋆(a + b); ε}; ∂_b(E), = (∂_b(a^⋆)) ⋅ {a + b} ∪ ∂_b(a + b); = (∂_b a) ⋅ {a^⋆(a + b)} ∪ ∅ ∪ {ε}; = ∅ ∪ {ε}; = {ε}
Q 44. Pour E = (ab + b)^⋆ba, calculer ∂_a(E) et ∂_b(E).
Cette définition de dérivée partielle est étendue à tout mot w ∈ Σ^⋆ et à des ensembles d'expressions rationnelles par : pour a ∈ Σ, w ∈ Σ^⋆ et S un ensemble d'expressions rationnelles,
∂_ε(E) = {E} ∂_(wa)(E) = ∂_a(∂_w(E)) ∂_w(S) = ⋃_(E ∈ S)∂_w(E)
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
{Q = {E_1|∃w ∈ Σ^⋆, E_1 ∈ ∂_w(E)}; I = {E}; F = {E_1 ∈ Q|ε ∈ L(E_1)}; T = {(E_1, c, E_2) ∈ Q × Σ × Q|E_2 ∈ ∂_c(E_1)}
On rappelle la notation w^(− 1)L de la partie I : pour tout mot w ∈ Σ^⋆ et tout langage L ⊂ Σ^⋆,
w^(− 1)L = {u ∈ Σ^⋆|wu ∈ L}
Q 45. Dessiner l'automate obtenu à partir de l'expression rationnelle E = (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^(− 1)u^(− 1)L = (uv)^(− 1)L.
Pour S ensemble d'expressions rationnelles, on note L(S) la réunion des langages des expressions de S. On admet que, si E est une expression rationnelle et x une lettre,
L(∂_x(E)) = x^(− 1)L(E)
Q 47. Soit S un ensemble d'expressions rationnelles sur Σ et w un mot de Σ^⋆. Montrer que
L(∂_w(S)) = w^(− 1)L(S).
Q 48. Montrer que pour tout mot w ∈ Σ^⋆, l'ensemble ∂_w(E) est l'ensemble des états accessibles depuis l'état E en lisant le motw.
Q 49. En déduire que l'automate d'Antimirov reconnait bien le langage de l'expression rationnelle E. Pour tout mot w ∈ Σ^⋆ et w ≠ ε, et pour toutes expressions rationnelles E et F sur Σ, on vérifie que
∂_w(E + F) = ∂_w(E) ∪ ∂_w(F); ∂_w(EF) ⊂ ∂_w(E) ⋅ F ∪ ⋃_(v ∈ S^+(w))∂_v(F); ∂_w(E^⋆) ⊂ ⋃_(v ∈ S^+(w))∂_v(E) ⋅ E^⋆
où S^+(w) est l'ensemble des suffixes non vides d'un mot w.
Pour une expression rationnelle E, on note
Q(E) = ⋃_(w ∈ Σ^⋆, w ≠ ε)∂_w(E).
Q 50. Montrer que pour toute expression rationnelle E, le cardinal de Q(E) est majoré par le nombre de lettres présentes dans l'écriture syntaxique de E (qu'on notera ‖E‖ ). Qu'en déduit-on sur l'automate d'Antimirov?

Questions fréquentes

4 questions
Sur quoi porte le sujet d'option informatique Centrale MP 2022 ?
Afficher ou masquer la section

Sur quoi porte le sujet d'option informatique Centrale MP 2022 ?

Le sujet porte sur les automates et les expressions rationnelles : miroir d'un langage, déterminisation, algorithme de Brzozowski, algorithme de Conway et dérivées d'Antimirov.

Ce sujet d'option informatique Centrale MP 2022 est-il difficile ?

Le jury le juge relativement long, avec une troisième partie plus difficile qui n'a été abordée sérieusement que dans les meilleures copies.

Quelles sont les erreurs les plus fréquentes relevées par le jury sur ce sujet d'option info Centrale MP 2022 ?

Le jury relève des oublis de parenthèses en OCaml, des confusions avec la syntaxe Python, une confusion entre caractère et variable, et une mauvaise gestion de la simplification récursive des expressions rationnelles.

Quels chapitres réviser pour ce sujet d'option informatique Centrale MP 2022 ?

Il faut maîtriser les langages, mots et automates finis, les expressions rationnelles, les algorithmes diviser pour régner et la programmation en OCaml.

Pas de description pour le moment