Corrigé Centrale 2025 Option informatique MP — Partie III, III.1 (Q22 à Q26) : Éléments minimaux d'un langage

Sujet officiel du concours Centrale, session 2025, épreuve Option informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

L'alphabet fini $Σ$ est totalement ordonné par $\leq$ . Sur $Σ^{*}$ , on pose $u_{1} \dots u_{n} ⪯ v_{1} \dots v_{m}$ ssi $n \leq m$ et $u_{i} \leq v_{i}$ pour tout $i \in [[1, n]]$ (ordre partiel dès que $∣Σ∣ \geq 2$ ; sur les mots d'une longueur $d$ fixée, c'est l'ordre produit de la partie II). Pour un langage $L$ , $min (L) = {u \in L ∣ ∄ v \in L, v ≺ u}$ . Exemples sur $Σ_{3} = {a, b, c}$ avec $a < b < c$ : $ab ≺ b c ≺ b c a ≺ cc ab$ ; $ab$ , $c a$ , $ba c$ sont deux à deux incomparables ; $min (Σ_{3}^{*}) = {ε}$ , $min (Σ_{3}^{+}) = {a}$ , $min ({ab, b c, c a, ba c, cc ab}) = {ab, c a, ba c}$ .

Q22. Montrer que $ε \in L ⟺ min (L) = {ε}$ .

Dans la suite, les langages ne contiennent pas $ε$ .

Q23. Montrer que si $L \subseteq Σ^{+}$ est non vide, alors $min (L) \neq = \emptyset$ (l'ordre $⪯$ est bien fondé).

On pose $L_{1} = {a^{i} b^{j} ∣ i, j \geq 1}$ et $L_{2} = {a^{i} b^{j} c^{k} ∣ i, j, k \geq 1, i \leq k, j \leq k}$ .

Q24. Donner $min (L_{1})$ sans justification ; montrer que $L_{1}$ et $min (L_{1})$ sont réguliers.
Q25. (a) Déterminer $min (L_{2})$ en expliquant brièvement. (b) Montrer que $L_{2}$ et $min (L_{2})$ ne sont pas réguliers (preuve détaillée pour $L_{2}$ , brève pour $min (L_{2})$ ).
Q26. Montrer que $min (L)$ peut être régulier sans que $L \subseteq Σ^{+}$ le soit.

Corrigé

Q22. Sens direct. Supposons $ε \in L$ . Pour tout mot $u$ , on a $ε ⪯ u$ (longueur $0 \leq ∣ u ∣$ et aucune lettre à comparer). Donc tout $u \in L$ différent de $ε$ vérifie $ε ≺ u$ et n'est pas minimal ; et $ε$ est minimal, car $v ⪯ ε$ impose $∣ v ∣ = 0$ , soit $v = ε$ . Ainsi $min (L) = {ε}$ .

Réciproque. Si $min (L) = {ε}$ , alors $ε \in min (L) \subseteq L$ .

(Un langage peut être infini : l'argument n'utilise aucune finitude.)

Q23. Soit $L \subseteq Σ^{+}$ non vide, $ℓ$ la plus petite longueur d'un mot de $L$ et $L_{ℓ} = L \cap Σ^{ℓ}$ , non vide. Comme $Σ$ est fini, $L_{ℓ}$ est fini ; muni de l'ordre lexicographique, total, il admet un minimum $u$ . Or, sur $Σ^{ℓ} = Σ \times \dots \times Σ$ , la relation $⪯$ est l'ordre produit ; d'après Q10, $u$ est minimal dans $L_{ℓ}$ pour $⪯$ . Montrons que $u \in min (L)$ : si $v \in L$ vérifie $v ≺ u$ , alors $∣ v ∣ \leq ∣ u ∣ = ℓ$ , donc $∣ v ∣ = ℓ$ par minimalité de $ℓ$ , et $v \in L_{ℓ}$ avec $v ≺ u$ : contradiction. Donc $min (L) \neq = \emptyset$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →