WikiPrépaLivrets

ENS Informatique Fondamentale (Maths Info) MP MPI 2023Sujet et corrigé

Pas encore noté
  • Automates finis et langages réguliers
  • Complexité asymptotique d'algorithmes
  • Algèbre linéaire (rang d'une matrice, sous-espace engendré)
  • Raisonnement par récurrence et construction d'automates
Logo concours ENS

Explorer les annales

BanqueX-ENSAnnée2023FilièreMP/MPIMatièreMathématiques-Informatique
Annales X-ENS MP/MPI Mathématiques-InformatiqueX-ENS MP/MPI 2023MP/MPI Mathématiques-InformatiqueMathématiques-Informatique 2023

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Lire en ligneLaTeXWord
  • Rapport du jury : non disponible

Présentation du sujet

Automates finis : ambiguïté, test d'ambiguïté et concision des automates
Afficher ou masquer la section

Le sujet porte sur les automates finis et leur propriété d'ambiguïté, c'est-à-dire l'existence de plusieurs calculs acceptants distincts pour un même mot. Il relie déterminisme et ambiguïté grâce à la notion d'automate miroir, construit un algorithme de test d'ambiguïté avec une analyse de complexité, puis démontre que les automates non ambigus peuvent être exponentiellement plus concis que les automates déterministes complets, tandis que les automates ambigus peuvent être exponentiellement plus concis que les automates non ambigus.

  1. 1PréambuleDéfinitions des automates finis, des calculs acceptants, du degré d'ambiguïté d'un mot et de l'ambiguïté d'un automate.
  2. 2Partie 1 : Déterminisme et ambiguïtéÉtude du lien entre déterminisme, co-déterminisme et ambiguïté d'un automate, à l'aide de la notion d'automate miroir, et construction de contre-exemples.
  3. 3Partie 2 : Test d'ambiguïtéConstruction d'un automate produit permettant de tester si un automate donné est ambigu, avec analyse de la complexité asymptotique de l'algorithme, puis généralisation à des mots de degré d'ambiguïté fixé.
  4. 4Partie 3 : Concision des automates non ambigusDémonstration que les automates non ambigus peuvent être exponentiellement plus concis que leurs équivalents déterministes complets, via l'étude du langage des mots dont la n-ième lettre en partant de la fin est un b.
  5. 5Partie 4 : Concision des automates ambigusDémonstration que les automates ambigus peuvent être exponentiellement plus concis que leurs équivalents non ambigus, via une étude par algèbre linéaire du rang d'une matrice associée au langage des mots contenant une lettre répétée.

Ces sujets peuvent vous intéresser

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

ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2023

VENDREDI 21 AVRIL 2023
14h00-18h00
FILIERES MP et MPI
Epreuve n^∘10
INFO-FONDAMENTALE (ULSR)
Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve

Épreuve d'informatique fondamentale Concision et ambiguïté

Le sujet porte sur les automates finis, dont la définition est rappelée dans le préambule. Le sujet s'intéresse à la propriété d'ambiguïté des automates finis, propriété également définie dans le préambule. La première partie lie les notions de déterminisme et d'ambiguïté d'un automate fini en utilisant la notion de miroir d'un automate. La deuxième partie amène à définir un algorithme qui teste si un automate est ambigu et vous demande de déterminer sa complexité asymptotique. La troisième et la quatrième partie étudient la concision des automates non ambigus et ambigus.
Les parties 1 et 2 sont indépendantes; il est conseillé de les traiter en premier car les parties 3 et 4 en dépendent. Il est permis d'admettre les réponses à certaines questions pour répondre aux suivantes.

Préambule

On note Σ un alphabet fini, c'est à dire un ensemble fini de symboles appelés lettres. Un mot sur Σ est une suite finie de lettres. On note Σ^n l'ensemble des mots de longueur n sur Σ et Σ^∗ l'ensemble de tous les mots sur Σ. Soient u, v deux mots sur Σ, on note u ⋅ v la concaténation de u et v. Un langage sur Σ est un sous-ensemble de Σ^∗.
Un automate sur Σ est un tuple A = (Q, T, I, F) où :
  • Q est un ensemble fini de symboles appelés états;
  • T ⊆ Q × Σ × Q est appelé ensemble des transitions;
    − I ⊆ Q est l'ensemble des états initiaux;
  • F ⊆ Q est l'ensemble des états finaux.
La Figure 1 représente graphiquement trois automates. Les symboles dans Q sont encerclés, avec deux cercles pour les symboles dans F. Une transition (q, a, q^′) ∈ T est représentée par une flèche étiquetée par a ∈ Σ, allant de l'état source q à l'état destination q^′. Les états initiaux sont indiqués par une flèche sans état source.
Un calcul de A sur un mot w = a_0…a_(n − 1) ∈ Σ^∗ est une suite finie d'états q_0…q_n ∈ Q^∗ telle que q_0 ∈ I et pour tout i < n, (q_i, a_i, q_(i + 1)) ∈ T. Un tel calcul est dit acceptant si q_n ∈ F. On dit alors que A accepte w. Le langage de A, noté L(A), est l'ensemble des mots acceptés par A.
Un automate A est dit déterministe si |I| ≤ 1 et pour tout (q, a) ∈ Q × Σ, |{q^′|(q, a, q^′) ∈ T}| ≤ 1.
Un automate A est dit complet si |I| ≥ 1 et pour tout (q, a) ∈ Q × Σ, |{q^′|(q, a, q^′) ∈ T}| ≥ 1.
Figure 1 - Trois automates reconnaissant le même langage
Soient w ∈ Σ^∗ et A un automate. Le mot w est dit ambigu pour A s'il existe deux calculs acceptants ρ et ρ^′ de A sur w avec ρ ≠ ρ^′. On définit d_A(w), le degré d'ambiguïté de w dans A, comme étant le nombre de calculs acceptants différents de A sur w. Ainsi, w est ambigu pour A si et seulement si d_A(w) > 1. On note Amb(A) l'ensemble des mots ambigus pour A. L'automate A est dit ambigu si Amb(A) ≠ ∅.
Ce sujet s'intéresse tout particulièrement aux automates non ambigus.

1 Déterminisme et ambiguïté

Question 1.1 Les trois automates de la Figure 1 acceptent le même langage. Donnez-en, sans justification, une description intuitive.
Question 1.2 Pour chacun des automates de la Figure 1, dites s'il est déterministe ou non déterministe. Justifiez vos affirmations.
Question 1.3 Pour l'automate A_1 de la Figure 1, calculez Amb(A_1) et déduisez en si A_1 est ambigu ou non. Faites de même pour les automates A_2 et A_3.
Soit A un automate. On note A˜ = (Q˜, T˜, I˜, F˜) l'automate miroir de A, défini par :
− Q˜ = Q;
− I˜ = F;
− F˜ = I;
− T˜ = {(t, a, s)|(s, a, t) ∈ T}.
Un automate est dit co-déterministe si son automate miroir est déterministe.
Question 1.4 Soit A un automate, w ∈ L(A) un mot accepté par A et q_0…q_n un calcul acceptant de A sur w. Montrez qu'il existe un mot w˜ tel que q_n…q_0 soit un calcul acceptant de A˜ sur w˜.
Question 1.5 Montrez qu'un automate A est ambigu si et seulement si A˜ est ambigu.
Question 1.6 Montrez que si un automate A est déterministe, alors A n'est pas ambigu.
Question 1.7 Montrez que si un automate A est co-déterministe, alors A n'est pas ambigu.
Question 1.8 Pour chacune des questions suivantes, donnez un automate A ayant au plus 4 états et respectant les propriétés demandées. Justifiez vos réponses.
(i) A est non ambigu mais ni déterministe, ni co-déterministe;
(ii) L(A) est infini et Amb(A) = L(A);
(iii) Amb(A) est infini, et Amb(A) ≠ L(A).

2 Test d'ambiguïté

Le but de cette partie est d'obtenir un algorithme qui teste si un automate est ambigu et de déterminer sa complexité asymptotique.
Dans cette partie, A est un automate (Q, T, I, F) tel que L(A) ≠ ∅.

2.1 Une construction utile

En utilisant A, on définit l'automate Aˆ = (Qˆ, Tˆ, Iˆ, Fˆ) comme suit :
− Qˆ = Q × Q × {0, 1};
− Iˆ = {(i, i, 0)|i ∈ I} ∪ {(i, i^′, 1)|i ∈ I, i^′ ∈ I, i ≠ i^′};
− Fˆ = {(f, f^′, 1)|f ∈ F, f^′ ∈ F};
− Tˆ = T_1 ∪ T_2 ∪ T_3 avec:
  • T_1 = {((s, s, 0), a, (t, t, 0))|(s, a, t) ∈ T};
  • T_2 = {((s, s, 0), a, (t, t^′, 1))|(s, a, t) ∈ T, (s, a, t^′) ∈ T, t ≠ t^′};
  • T_3 = {((s, s^′, 1), a, (t, t^′, 1))|(s, a, t) ∈ T, (s^′, a, t^′) ∈ T}.
Question 2.1 Soit A_1 le premier automate de la figure Figure 1. Construisez l'automate Aˆ_1. Il est inutile de faire figurer les états qui ne sont pas accessibles à partir d'un état initial. Donnez, sans justification, le langage L(Aˆ_1).
Question 2.2 Soient w ∈ Σ^∗ un mot et ρ = (q_0, q_0^′, b_0)…(q_n, q_n^′, b_n) un calcul de Aˆ sur w. On pose μ = q_0…q_n et μ^′ = q_0^′, …, q_n^′.
(i) Montrez que μ et μ^′ sont des calculs de A sur w.
(ii) Montrez que b_n = 0 si et seulement si μ = μ^′.
(iii) Montrez que, si ρ est acceptant, alors μ et μ^′ sont acceptants.
(iv) Montrez qu'il existe un calcul ρ tel que μ et μ^′ sont acceptants mais ρ ne l'est pas.
Question 2.3 Montrez que L(Aˆ) = Amb(A).

2.2 L'algorithme

Pour deux fonctions f, g : ℕ → ℕ, on dit que g est une borne asymptotique de f, et on le note par f ∈ O(g), s'il existe deux constantes strictement positives n_0 ∈ ℕ et c ∈ ℕ telles que pour tout n ≥ n_0, f(n) ≤ c × g(n). Cette définition se généralise naturellement à des fonctions f et g avec plusieurs paramètres.
Question 2.4 Pour chaque ensemble Qˆ, Tˆ, Iˆ et Fˆ, donnez une borne asymptotique au nombre d'éléments qu'il contient en fonction des tailles de Q, T, I et F.
Question 2.5 Donnez un algorithme qui a comme entrée A et comme sortie Aˆ en précisant:
(i) quelle structure de données classique (matrice d'adjacence ou liste d'adjacence) est utilisée pour représenter A et Aˆ,
(ii) une borne asymptotique de la complexité en temps d'exécution de cet algorithme en fonction de la somme des tailles des ensembles Q, T, I et F.
Question 2.6 Décrivez une méthode permettant de tester si A est ambigu en utilisant l'automate Aˆ. Donnez une borne asymptotique de la complexité en temps de cette méthode en fonction de la somme des tailles des ensembles Q, T, I et F.

2.3 Généralisation

Soit k un entier strictement positif.
Question 2.7 Soit w ∈ L(A) un mot de longueur k.
(i) Donnez, en fonction de k et |Q|, une borne supérieure sur le degré d'ambiguïté de w dans A.
(ii) Donnez un automate A et un mot de longueur k pour lesquels la borne supérieure indiquée ci-dessus est atteinte.
Question 2.8 On pose Amb_(≥ k)(A) = {w ∈ L(A)|d_A(w) ≥ k}. Montrez que Amb_(≥ k)(A) est régulier.
Question 2.9 On pose Amb_k(A) = {w ∈ L(A)|d_A(w) = k}. Montrez que Amb_k(A) est régulier.

3 Concision des automates non ambigus

Le but de cette partie est de prouver que les automates non ambigus peuvent être exponentiellement plus concis que leurs équivalents déterministes et complets.
Dans toute cette partie, on fixe l'alphabet Σ = {a, b}. Pour n ≥ 1 un entier, on pose L_n = {w_1 ⋅ b ⋅ w_2|w_1, w_2 ∈ Σ^∗, |w_2| = n − 1}, le langage des mots dont la n-ième lettre en partant de la fin est un b.
Question 3.1 Donnez un automate non ambigu acceptant L_3, puis donnez un automate déterministe et complet acceptant L_3.
Question 3.2 Montrez que pour tout n ≥ 1 entier, il existe un automate non ambigu A avec n + 1 états tel que L(A) = L_n.
Question 3.3 Montrez que pour tout n ≥ 1 entier, il existe un automate déterministe et complet B avec 2^n états tel que L(B) = L_n.
On veut à présent prouver que tout automate déterministe et complet acceptant L_n a au moins 2^n états.
Question 3.4 Soit B un automate déterministe et complet. Soit w ∈ Σ^∗. Montrez qu'il existe un unique calcul, non nécessairement acceptant, de B sur w.
Soit B un automate déterministe et complet et w ∈ Σ^∗. On note q_w l'état atteint par l'unique calcul de B sur w, c'est-à-dire l'état q_m tel que q_0…q_m est un calcul de B sur w.
Question 3.5 Soit n ∈ ℕ et B un automate déterministe et complet reconnaissant L_n. Soient w et w^′ deux mots de Σ^∗ de longueur n. Montrez que q_w = q_(w^′) si et seulement si w = w^′.
Question 3.6 Soit n ∈ ℕ. Montrez que tout automate déterministe et complet reconnaissant L_n a au moins 2^n états.

4 Concision des automates ambigus

Le but de cette partie est de prouver que les automates ambigus peuvent être exponentiellement plus concis que leurs équivalents non ambigus.
Pour n ∈ ℕ, on pose Σ_n un alphabet à n lettres et K_n le langage des mots sur Σ_n^∗ dont au moins une lettre apparaît au moins deux fois, c'est-à-dire :
K_n = {w_1 ⋅ x ⋅ w_2 ⋅ x ⋅ w_3|w_1, w_2, w_3 ∈ Σ_n^∗, x ∈ Σ_n}
Question 4.1 Pour Σ_3 = {a, b, c},
(i) donnez un automate acceptant K_3 et ayant au plus 5 états,
(ii) donnez un automate non ambigu acceptant K_3 et ayant au plus 9 états.
Question 4.2 Montrez que pour tout n ∈ ℕ, il existe un automate avec au plus n + 2 états acceptant K_n.
Question 4.3 Montrez que pour tout n ∈ ℕ, il existe un automate non ambigu avec au plus 2^n + 1 états acceptant K_n.
On veut à présent prouver que tout automate non ambigu acceptant K_n a au moins 2^n + 1 états. Jusqu'à la fin de cette partie, on fixe un entier n ≥ 2 et un automate non ambigu A = (Q, T, I, F) acceptant K_n.
Soient u et v deux mots de Σ_n^∗. Lorsque u ⋅ v ∈ K_n, on note q_(u, v) l'état de A atteint après avoir lu u lors de l'unique calcul acceptant de A sur u ⋅ v. Autrement dit, soit ℓ = |u| et q_0…q_m l'unique calcul acceptant de A sur u ⋅ v, alors q_(u, v) = q_ℓ.
Question 4.4 Soient u, u^′ et v, v^′ quatre mots de Σ_n^∗ tels que u ⋅ v ∈ K_n et u^′ ⋅ v^′ ∈ K_n. On suppose que q_(u, v) = q_(u^′, v^′).
(i) Montrez que u ⋅ v^′ ∈ K_n et u^′ ⋅ v ∈ K_n.
(ii) Montrez que q_(u, v) = q_(u, v^′) = q_(u^′, v) = q_(u^′, v^′).
L'objectif à présent est de prouver que ces contraintes garantissent que A a au moins 2^n états.
Soit s = (s_i) une suite de mots et α une lettre. On note s ⋅ α la suite ( s_i ⋅ α ), c'est-à-dire la suite obtenue en ajoutant α à la fin de chaque mot de s.
On fixe un ordre total < surΣ_n, et on note Σ_n = {α_1, …, α_n} avec pour tout 1 ≤ i < j ≤ n, α_i < α_j. On construit une famille s^0, …, s^n de suites de mots de Σ_n comme suit :
  • s^0 est la suite contenant uniquement ε;
  • Pour 0 < i ≤ n, s^i = s^(i − 1), s^(i − 1) ⋅ α_i, la suite constituée de s^(i − 1), suivie de la suite s^(i − 1) ⋅ α_i.
Finalement, on pose s = s^n. Par exemple, pour n = 2, Σ_2 = {a, b} et a < b, la suite s contient 4 éléments : s_0 = ε, s_1 = a, s_2 = b, s_3 = ab.
Finalement, on remarque que s contient 2^n éléments et on pose M_n la matrice de dimension 2^n × 2^n à coefficients en ℝ définie par :
M_n[i, j] = {1 si s_i et s_j ont une lettre en commun; 0 sinon
Par exemple, M_2 est donnée ci-dessous :
M_2 = (0, 0, 0, 0; 0, 1, 0, 1; 0, 0, 1, 1; 0, 1, 1, 1)
Question 4.5 Montrez que M_n peut s'écrire sous la forme:
M_n = (M_(n − 1), M_(n − 1); M_(n − 1), 1_(n − 1))
où, pour n ≥ 1, 1_n est la matrice carrée de dimension 2^n × 2^n dont tous les coefficients valent 1 .
Question 4.6 Soient i < 2^n et j < 2^n. Montrez que M_n[i, j] = 1 si et seulement si s_i ⋅ s_j ∈ K_n.
À chaque état q de A, on associe le vecteur colonne v_q de dimension 2^n défini par :
v_q[i] = {1 s'il existe j < 2^n tel que q = q_(s_i, s_j); 0 sinon
Question 4.7 Montrez que l'ensemble de vecteurs (v_q)_(q ∈ Q) est une famille génératrice du sousespace vectoriel engendré par les vecteurs colonnes de M_n.
Indication : Soit u_j la j-ème colonne de M_n. On pourra montrer que u_j est une combinaison linéaire de vecteurs de (v_q)_(q ∈ Q) en prouvant que :
u_j = ∑_(q ∈ Q; ∃i, q = q_(s_i, s_j))v_q
Question 4.8 Montrez que M_n est de rang 2^n − 1.
Question 4.9 En déduire que A contient au moins 2^n − 1 états q tels que v_q ≠ 0.
Question 4.10 Montrez que si v_q ≠ 0, alors q ∉ I et q ∉ F.
Question 4.11 Conclure que A a au moins 2^n + 1 états.

Questions fréquentes

4 questions
Sur quels chapitres porte le sujet info-fondamentale ENS MP-MPI 2023 ?
Afficher ou masquer la section

Sur quels chapitres porte le sujet info-fondamentale ENS MP-MPI 2023 ?

Il porte sur les automates finis et les langages réguliers, l'analyse de complexité d'algorithmes et l'algèbre linéaire, mobilisée en dernière partie pour minorer le nombre d'états d'un automate.

Quelles parties du sujet ENS info-fondamentale MP-MPI 2023 sont indépendantes ?

Les parties 1 et 2 sont indépendantes entre elles et il est conseillé de les traiter en premier, car les parties 3 et 4 s'appuient sur leurs résultats.

Le sujet ENS MP-MPI 2023 nécessite-t-il des connaissances avancées d'algèbre linéaire ?

La partie 4 utilise le rang d'une matrice et la notion de famille génératrice d'un sous-espace vectoriel pour minorer le nombre d'états d'un automate non ambigu.

Ce sujet porte-t-il sur la théorie des langages ou sur l'algorithmique ?

Les deux : il définit et manipule des automates finis (théorie des langages), demande la conception d'un algorithme de test d'ambiguïté avec sa complexité, puis prouve des résultats de concision par des arguments combinatoires et algébriques.

Pas de description pour le moment