J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Centrale Option Informatique MP 2022

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo centrale
🔗 Explorer
Banque
Centrale
Année
2022
Filière
MP
Matière
Info
Centrale MPCentrale 2022MP InfoInfo 2022
2025_08_29_ba5fbeeeeec890e6f856g

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 est son nombre de lettres et se note . Le mot vide, noté , est le seul mot de longueur nulle.
Si un mot est de longueur , on le note , où les sont des lettres de .
Un langage sur l'alphabet est un ensemble .
L'étoile de Kleene d'un langage , notée , est le plus petit langage qui inclut , qui contient et qui est stable par concaténation.
La concaténation de deux langages et est notée , souvent abrégé en lorsqu'il n'y a pas d'ambiguïté.

Automates finis

Un automate fini non déterministe sur un alphabet est un quadruplet , où est un ensemble fini d'états, est le sous-ensemble des états initiaux, est le sous-ensemble des états finaux et l'ensemble est l'ensemble des transitions, étiquetées par les lettres de l'alphabet .
Si , on note 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 est reconnu par l'automate s'il existe une succession de transitions:
On dira que le mot étiquette un chemin dans l'automate allant de à .
Le langage d'un automate , noté , est exactement l'ensemble des mots reconnus par l'automate . On dit alors que reconnait . 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 , où l'ensemble des états initiaux est un singleton (un unique état initial) et où l'ensemble des transitions est remplacé par une fonction de transition définie sur un sous-ensemble de et à valeurs dans . Pour chaque couple , il existe au plus une transition ( ) qui, si elle existe, est telle que .
L'automate est déterministe complet si la fonction de transition est définie sur . Dans ce cas, on définit la fonction de transition étendue sur par
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 d'un automate implémenté étant toujours supposé être un intervalle d'entiers .
Figure 1 L'automate
Par exemple, l'automate 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 sont des expressions rationnelles, pour toute lettre ;
  • si et sont deux expressions rationnelles, alors et sont des expressions rationnelles.
La sémantique des expressions rationnelles est définie par l'application qui associe à toute expression rationnelle un langage rationnel sur par:
et, si et sont deux expressions rationnelles,
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 , 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ù est une fonction usuelle simple et où et 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 de longueur , on définit son mot miroir par . Par convention, le mot vide est son propre miroir.
Pour tout langage , on définit son langage miroir constitué de l'ensemble des mots miroirs du langage :
Q 1. Décrire le langage de l'automate de l'exemple de la figure 1 et décrire son langage miroir .
Q 2. Dessiner un automate , reconnaissant le langage miroir .
Soit un automate non déterministe et le langage qu'il reconnait.
Q 3. Donner, en justifiant, la construction de l'automate miroir qui reconnait le langage .
Q 4. Écrire une fonction transpose de signature automate automate qui étant donné un automate non déterministe en entrée, renvoie un automate non déterministe qui reconnait le miroir de .
Q 5. Quelle est la complexité de cette fonction ?

I.B - Palindromes et rationalité

Soit . On dit que le mot est un palindrome si .
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 (String.length ), le -ième caractère de la chaine de caractères est obtenu par l'expression s. [i].
Pour un alphabet , on note l'ensemble des palindromes de .
Q 7. Montrer que si est un alphabet à une lettre, alors est rationnel.
Q 8. Montrer que si contient au moins deux lettres, alors n'est pas rationnel.
On pourra utiliser un automate et un mot de .
Soit un langage reconnu par l'automate .
Pour , on note le langage de tous les mots qui étiquettent un chemin dans partant de et arrivant en .
Q 9. Montrer que est reconnaissable et exprimer le langage en fonction de langages .
Q 10. Montrer que .
Soit un langage rationnel reconnu par un automate .
On définit les langages et .
Q 11. Décrire simplement les langages et .
Q 12. Les langages et sont-ils reconnaissables ?
On pourra faire intervenir les langages , définis ci-dessus.

I. Déterminisation

On rappelle que pour tout automate non déterministe, on peut définir l'automate déterminisé accessible où est l'ensemble des états accessibles depuis l'état initial dans l'automate des parties. Cet automate déterminisé accessible reconnait le même langage que l'automate .
Q 13. Écrire un automate non déterministe à 4 états qui reconnait le langage . 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 afin d'obtenir l'automate . Les états de seront renommés .
Q 15. Appliquer l'algorithme de déterminisation sur l'automate miroir afin d'obtenir l'automate . Ses états seront renommés
Q 16. Quel doit être le langage reconnu par l'automate ?
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 (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 tel que , toute partie de va être représentée par un entier entre 0 et . Dans la suite, on supposera . Soit une partie de . On définit le numéro de par la fonction suivante
On se donne pow un tableau des puissances de 2 , qui contient toutes les puissances , pour .
let pow = Array.make 21 1 ;;
    for i = 1 to 20 do
        pow.(i) <- pow.(i-1) * 2
    done ;;
Soit un état et le numéro d'un ensemble d'états , c'est-à-dire numero .
Q 19. Écrire une fonction est_dans de signature int int bool qui teste, à l'aide d'opérations arithmétiques, si l'état est dans l'ensemble d'états représenté par le numéro en opérations.
Soit une liste d'états contenant éventuellement plusieurs fois le même état, représentant l'ensemble .
Q 20. Écrire une fonction numero de signature int list int qui calcule le numéro de l'ensemble .
Par exemple représente l'ensemble , de numéro .
Soit une liste d'états et un ensemble d'états représenté par son numéro .
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 représenté par .
On prépare désormais la fonction de transition de l'automate déterminisé accessible.
Soit un ensemble d'états de . On suppose désormais que l'automate est sur l'alphabet à deux lettres .
On cherche à calculer la fonction de transition de l'automate déterminisé. On rappelle que, pour et ,
La transition ( ) sera alors dans l'automate déterminisé.
En parcourant l'ensemble des transitions de l'automate, on va simultanément calculer les états ( ), ce qui correspond à la table de transition depuis l'état .
Q 22. Écrire une fonction etat_suivant de signature int (intcharint) list (intint) qui, étant donné en entrée un entier tel que et la liste des transitions , calcule le couple d'entiers ( ) tels que et .
Au moment de construire l'automate déterminisé accessible , on va être amené à renommer (c'est-à-dire ici renuméroter) les états de pour avoir au final un ensemble d'états de la forme où sera le nombre de parties de accessibles dans l'automate des parties. Pour cela, on va simplement utiliser une liste contenant des couples ( ) où est le numéro d'un ensemble d'états et le numéro final par lequel sera remplacé. Par exemple, si à un moment donné de l'algorithme, la liste contient ( 6,2 ), "l'ensemble d'états 6 " (qui correspond dans à ) 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 dans une liste comme ci-dessus ( -1 si 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 de et du nombre d'états 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 qui reconnait le langage et tel que l'automate miroir est déterministe et accessible.
On note le déterminisé accessible de .
Si est un mot et un langage, on note .
Q 26. Soit un état et un mot. Montrer que si , alors il existe un mot tel que .
Q 27. Montrer la propriété () : si l'on prend deux mots et dans tels que , alors dans l'automate déterminisé, .
Q 28. En déduire que si est un automate quelconque reconnaissant , alors en posant , montrer que reconnait 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 , (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
où la notation signifie que les langages représentés sont égaux : .
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 , où lettres concaténées se succèdent.
Figure 2 Exemple de l'arbre syntaxique de l'expression
Q 33. Combien d'applications de règles décrites ci-dessus sont-elles nécessaires pour obtenir à partir de l'expression équivalente ?
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 est la matrice de taille où chaque coefficient vaut .
La matrice identité de taille est la matrice de taille où chaque coefficient vaut sur la diagonale et en dehors de la diagonale.
On définit la somme de deux matrices et de taille ( ) par la matrice de taille ( ) où où le + représente l'opération rationnelle d'union et .
On définit le produit de deux matrices et de taille et à la manière du produit matriciel usuel , de taille ( ), 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 ( ). 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 ( ) et la seconde de taille .) 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 , où et sont quatre lettres.
On associe à cette matrice le graphe étiqueté à deux sommets de la figure 3 .
Figure 3
On note le langage de l'automate , où .
Q 37. Donner une expression rationnelle sur l'alphabet pour décrire chaque langage .

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 de la matrice carrée :
  • si la taille vaut , donc ;
  • sinon, pour de taille , on découpe par blocs
où et sont carrées de taille , et on définit
où
On suppose déjà codées les deux fonctions suivantes sur les matrices d'expressions rationnelles :
  • (decouper m n1 n2) renvoie quatre matrices blocs et telles que est carrée de taille est carrée de taille et , où la matrice d'entrée est carrée de taille .
decouper : mat -> int -> int -> (mat*mat*mat*mat)
  • (recoller a b c d) renvoie la matrice à partir des quatre blocs et codés par dont les tailles sont compatibles.
recoller : mat -> mat -> mat -> mat -> mat
On propose la décomposition récursive suivante pour une matrice carrée de taille ,
où est une lettre et est carrée de taille . Ainsi,
où
Q 38. Évaluer les différentes complexités des sommes et produits effectués, et en déduire que si est la complexité du calcul de l'étoile pour une matrice de taille , alors . En déduire la complexité de cet algorithme.
On se place dans le cas où la taille de la matrice est une puissance de 2 , avec .
On propose désormais la décomposition récursive suivante
où les matrices et sont carrées de taille chacune.
Q 39. Évaluer les différentes complexités des sommes et produits effectués, et en déduire que si est la complexité du calcul de l'étoile pour une matrice de taille , alors . En déduire la complexité de cet algorithme.
Q 40. Comment gérer le cas des matrices de taille quelconque ? Quelle complexité peut-on obtenir pour le calcul de ?
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 un automate, où l'ensemble d'états est .
On définit la matrice de transition de l'automate par la matrice d'expressions rationnelles de taille ( ) telle que pour s'il existe au moins une telle lettre sinon.
On admet la propriété suivante : pour tout état , où est le langage défini en question 9.
Q 42. Montrer que
où est une matrice ligne d'expressions rationnelles de la forme où chaque , et est une matrice colonne d'expressions rationnelles de la forme où chaque . On précisera les valeurs de et en fonction de l'automate .
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 et sont deux ensembles d'expressions rationnelles, on convient que
En particulier, on a et .
Soit une expression rationnelle sur un alphabet et soit une lettre. On définit la dérivée partielle de par , notée , comme un ensemble d'expressions rationnelles défini inductivement par
ù
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 , on calcule et ainsi : comme ,
Q 44. Pour , calculer et .
Cette définition de dérivée partielle est étendue à tout mot et à des ensembles d'expressions rationnelles par : pour et un ensemble d'expressions rationnelles,
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 défini par
On rappelle la notation de la partie I : pour tout mot et tout langage ,
Q 45. Dessiner l'automate obtenu à partir de l'expression rationnelle . On indiquera précisément l'ensemble d'états .
Q 46. Montrer que pour tous mots et tout langage .
Pour ensemble d'expressions rationnelles, on note la réunion des langages des expressions de . On admet que, si est une expression rationnelle et une lettre,
Q 47. Soit un ensemble d'expressions rationnelles sur et un mot de . Montrer que
Q 48. Montrer que pour tout mot , l'ensemble est l'ensemble des états accessibles depuis l'état en lisant le .
Q 49. En déduire que l'automate d'Antimirov reconnait bien le langage de l'expression rationnelle . Pour tout mot et , et pour toutes expressions rationnelles et sur , on vérifie que
où est l'ensemble des suffixes non vides d'un mot .
Pour une expression rationnelle , on note
Q 50. Montrer que pour toute expression rationnelle , le cardinal de est majoré par le nombre de lettres présentes dans l'écriture syntaxique de (qu'on notera ). Qu'en déduit-on sur l'automate d'Antimirov?
Centrale Option Informatique MP 2022 - Version Web LaTeX | WikiPrépa | WikiPrépa