Corrigé CCINP 2026 Informatique MP — Problème 2 (II) (Q25 à Q28) : Du trie à l'automate minimal

Sujet officiel du concours CCINP, session 2026, épreuve Informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

On interprète un trie (Q14 à Q24) comme un automate dont les mots reconnus sont ceux du trie.

Q25. Préciser les composants de cet automate : états, états initiaux, états finaux, transitions, alphabet.
Q26. Dessiner l'automate associé au trie de Q14 (mots en, entier, bot, bottier, bottine, routier, routine).

Cet automate est déterministe : depuis un état $q$ , la lecture de la lettre $c$ mène à au plus un état $δ (q, c)$ ; sinon, on parle de blocage. On note $Σ$ l'alphabet. Deux états sont en relation, $q E q^{'}$ , si :

$q$ et $q^{'}$ sont tous deux finaux, ou tous deux non finaux ;
pour toute lettre $c \in Σ$ , soit $c$ est un blocage pour $q$ et pour $q^{'}$ , soit $δ (q, c) E δ (q^{'}, c)$ .

Q27. Donner, dans l'automate de Q26, deux états sans transition sortante en relation pour $E$ , puis deux états avec transitions sortantes en relation pour $E$ .

On admet que deux états en relation pour $E$ reconnaissent le même langage (lecture commencée depuis l'un ou l'autre).

Q28. En déduire une façon de réduire au plus le nombre d'états de l'automate d'un trie sans changer le langage reconnu : grandes lignes, justification, et illustration sur le trie de ${car, par, cal, pal}$ .

Corrigé

Q25. Pour un trie $t$ :

états : les nœuds de $t$ ; chacun est identifié au mot épelé par le chemin qui y mène depuis la racine, donc à un préfixe d'un mot de l'ensemble ;
état initial : un seul, la racine (le mot vide) ;
états finaux : les nœuds étiquetés true ;
transitions : $(q, c, q^{'})$ chaque fois que $q^{'}$ est l'enfant de $q$ d'étiquette $c$ ; dans le type OCaml, un couple (c, q') de la liste d'enfants de $q$ ;
alphabet : les lettres (le type char), ou seulement celles qui apparaissent dans les mots.

Chaque nœud ayant au plus un enfant par lettre, l'automate est déterministe ; il n'est pas complet (blocages). Le graphe sous-jacent est l'arbre lui-même : pour tout mot $w$ , il existe au plus un chemin étiqueté $w$ depuis l'état initial, qui aboutit au nœud de $w$ . Le mot est donc reconnu si et seulement si ce nœud existe et porte true, c'est-à-dire si et seulement si $w$ appartient au trie : le langage reconnu est l'ensemble des mots du trie.

Q26. États numérotés dans l'ordre de lecture des branches : $0 = ε$ ; branche « e » : $1 =$ e, $2 =$ en, …, $6 =$ entier ; branche « b » : $7 =$ b, …, $13 =$ bottier, $14 =$ bottin, $15 =$ bottine ; branche « r » : $16 =$ r, …, $22 =$ routier, $23 =$ routin, $24 =$ routine. Les finaux (doublement cerclés) sont $2, 6, 9, 13, 15, 22, 24$ .

Il a 25 états (un par nœud du trie) et 24 transitions (une par arête).

Q27. Sans transition sortante : les états $6$ (entier) et $13$ (bottier). Tous deux sont finaux et toute lettre est un blocage pour l'un comme pour l'autre : la seconde condition est vraie pour toutes les lettres, donc $6 E 13$ . De même, les cinq feuilles $6, 13, 15, 22, 24$ sont deux à deux en relation.

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 →