WikiPrépaLivrets

ENS Informatique MP 2001Sujet

2,7(3 votes)
  • Monoïdes de mots et morphismes
  • Automates et langages formels
  • Algorithmique et analyse de complexité
  • Suites infinies et systèmes dynamiques symboliques
  • Récurrence et démonstrations combinatoires
Logo concours ENS

Explorer les annales

BanqueX-ENSAnnée2001FilièreMPMatièreInformatique
Annales X-ENS MP InformatiqueX-ENS MP 2001MP InformatiqueInformatique 2001

Téléchargements

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

Présentation du sujet

Mots infinis engendrés par des L-systèmes (morphismes, systèmes D0L et HD0L) et mots sans carré
Afficher ou masquer la section

Le sujet étudie les mots infinis engendrés par des morphismes de monoïdes de mots, appelés L-systèmes, introduits à l'origine pour modéliser la croissance d'organismes vivants. La première partie définit les D0L-systèmes et HD0L-systèmes et leurs langages associés. La deuxième étudie les conditions sous lesquelles un tel système engendre un mot infini, avec l'exemple du mot de Thue-Morse. La troisième établit une hiérarchie stricte entre huit classes de L-systèmes selon les mots infinis qu'ils peuvent engendrer.

  1. 1Partie 1 : morphismes et L-systèmesDéfinir les morphismes de mots, les D0L-systèmes et HD0L-systèmes, et étudier des exemples de langages associés, notamment un langage non rationnel.
  2. 2Partie 2 : mots infinis engendrés par L-systèmesCaractériser les conditions sous lesquelles un langage ou un L-système engendre un mot infini, étudier les lettres mortelles et immortelles, un algorithme de détection, et construire le mot infini de Thue-Morse.
  3. 3Partie 3 : hiérarchie des classes de L-systèmesÉtablir des inclusions strictes ou des égalités entre huit classes de L-systèmes (D0L, PD0L, CD0L, ND0L, HD0L, etc.) selon les mots infinis qu'elles peuvent engendrer.
  4. 4Partie 4 : mots sans carré et mots sans cubeÉtudier les mots sans carré, construire un algorithme de détection, montrer qu'un morphisme particulier préserve l'absence de carré, en déduire l'existence d'une infinité de mots sans carré, et montrer que le mot de Thue-Morse est sans cube.

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

SESSION 2001

Filière MP

INFORMATIQUE

(Épreuve commune aux ENS: Ulm, Lyon et Cachan)
Durée : 4 heures
L'usage de la calculatrice n'est pas autorisé
Les correcteurs attendent des réponses précises et concises aux questions posées. On demande à plusieurs reprises de proposer des algorithmes. On exprimera ces algorithmes avec un point de vue de haut niveau, sans décrire leur implantation effective (cf l'algorithme proposé dans l'énoncé de la question 2.9). La complexité d'un algorithme doit toujours être interprétée comme le nombre d'opérations élémentaires (calculs, comparaisons, ...) nécessaires à son exécution.
La partie 4 est largement indépendante des parties précédentes. En règle générale, les références à un résultat d'une autre partie sont explicitement mentionnées.
Soit A un alphabet, c'est à dire un ensemble fini non vide. On note A^∗ l'ensemble des mots finis formés de lettres de A, y compris le mot vide ε, et A^+ = A^∗∖{ε}. Si u et v sont deux mots, on note uv le mot obtenu par concaténation de u et v; l'ensemble A^∗ muni de cette loi de composition est un monoïde. On note |w| la longueur d'un mot w.
On dit qu'un mot v est facteur d'un autre mot w s'il existe des mots x et y tels que w = xvy. Si de plus on peut prendre x = ε, le mot v est dit préfixe de w, tandis que si y = ε, le mot v est dit suffixe de w.
Dans les exemples, on utilisera le plus souvent les alphabets A_1 = {a}, A_2 = {a, b} et A_3 = {a, b, c}.
L'ensemble des lettres de A qui apparaissent effectivement dans un mot w ∈ A^∗ est noté Alph (w). Le cardinal d'un ensemble S est noté Card(S). On note S ⊂ T quand l'ensemble S est inclus (au sens large) dans l'ensemble T.

1 Morphismes et L-systèmes

Soient A et B deux alphabets. Un morphisme de A^∗ dans B^∗ est une application f : A^∗ → B^∗ telle que, pour tous mots u et v dans A^∗, f(uv) = f(u)f(v).

Question 1.1.

Montrer qu'un morphisme f : A^∗ → B^∗ est entièrement défini par la donnée de f(x) pour chaque lettre x ∈ A.
Cette observation permet d'exprimer les morphismes de manière plus compacte. Ainsi, on notera f = (a ↦ aab, b ↦ ba, c ↦ ε) l'unique morphisme de A_3^∗ dans A_2^∗ tel que f(a) = aab, f(b) = ba et f(c) = ε.
Un morphisme f : A^∗ → B^∗ est dit non-effaçant si f(x) ≠ ε pour tout x ∈ A, effaçant dans le cas contraire; il est dit lettre-à-lettre si f(x) ∈ B pour tout x ∈ A.
Si f est un morphisme de A^∗ dans lui-même, on note f^1 = f, f^2 = f ∘ f et plus généralement f^(n + 1) = f^n ∘ f.
On appelle DOL-système un triplet G = (A, f, u_0), où A est un alphabet, f est un morphisme de A^∗ dans A^∗ et u_0 ∈ A^∗ ( u_0 est appelé l'axiome du D0L-système G ).
À chaque D0L-système G = (A, f, u_0), on associe la suite infinie de mots S(G) = (u_0, u_1, u_2, …) telle que u_0 est l'axiome de G et u_(n + 1) = f(u_n) pour tout n ∈ ℕ, ce qu'on peut noter u_n = f^n(u_0). On associe aussi à G le langage L(G) = {u_0, u_1, u_2, …} = {f^n(u_0) : n ∈ ℕ}.
Par exemple, soit G_1 = (A_2, (a ↦ b, b ↦ aa), a). On a
S(G_1) = (a, b, aa, bb, aaaa, bbbb, …)
et L(G_1) = {a^(2^i), b^(2^i) : i ∈ ℕ}.

Question 1.2.

Construire un DOL-système G_2 tel que L(G_2) = L(G_1) mais S(G_2) ≠ S(G_1).

Question 1.3.

Soit θ le morphisme de A_2^∗ dans A_2^∗ défini par θ(a) = ab et θ(b) = ba. On considère le D0L-système T = (A_2, θ, a). Calculer les cinq premiers termes de S(T). En utilisant un morphisme lettre-à-lettre ι : A_2^∗ → A_2^∗, donner une formule simple permettant de passer de θ^n(a)a˙θ^(n + 1)(a). Quelle est la longueur de θ^n(a) ? En déduire que L(T) n'est pas un langage rationnel.
On appelle HD0L-système un quintuplet H = (B, f, u_0, A, g), où A et B sont des alphabets (éventuellements égaux), ( B, f, u_0 ) est un D0L-système que l'on notera H^0, et g est un morphisme de B^∗ dans A^∗. Si S(H^0) = (u_0, u_1, u_2, …) est la suite de mots associée à H^0, alors on associe à H la suite S(H) = (g(u_0), g(u_1), g(u_2), …) et le langage L(H) = {g(f^n(u_0)) : n ∈ ℕ}.

Question 1.4.

Soit H = (A_2, (a ↦ ab, b ↦ b), a, A_1, (a ↦ a, b ↦ a)). Montrer que L(H) = A_1^+.
Existe-t-il un D0L-système G tel que L (G) = L(H) ?
Note historique : les D0L-systèmes et les HD0L-systèmes, ainsi que d'autres systèmes similaires permettant de construire des langages, sont collectivement appelés L-systèmes. Ils ont été introduits en 1968 par Aristid Lindenmayer pour modéliser la croissance de certains organismes vivants.

2 Mots infinis engendrés par L-systèmes

Soit A un alphabet. Un mot infini sur A est une suite y = (y_i)_(i ∈ ℕ) à valeurs dans A. On note A^ℕ l'ensemble de tous les mots infinis sur A. Un préfixe de y est un mot (fini) de la forme y_0 y_1…y_(k − 1), avec k ∈ ℕ, et un facteur de y est un mot de la forme y_i y_(i + 1)…y_(i + k − 1), avec i, k ∈ ℕ.
Soit L ⊂ A^∗ un langage et y ∈ A^ℕ un mot infini. On dit que L engendre le mot infini y si les deux conditions suivantes sont vérifiées :
(i) L est infini;
(ii) tout élément de L est préfixe de y.

Question 2.1.

Montrer que si le langage L engendre deux mots infinis y et z, alors y = z. Montrer que quel que soit le mot infini y, il existe au moins un langage qui engendre y.

Question 2.2.

Montrer qu'un langage L engendre un mot infini si et seulement si L est infini et pour tout couple ( u, v ) d'éléments de L, soit u est préfixe de v, soit v est préfixe de u.
Si G est un D0L-système (ou un HD0L-système), et si L(G) engendre un mot infini y, on dit aussi que G engendre y, et on note y = W(G).
Dans les questions 2.3, 2.5, 2.6 et 2.7, il est demandé de construire un D0L-système ayant certaines propriétés; à chaque fois, un seul exemple suffit : on ne cherchera pas à caractériser tous les D0L-systèmes ayant les propriétés requises ni à prouver l'unicité de l'exemple construit.

Question 2.3.

Donner un DOL-système Q engendrant le mot infini q = (q_i)_(i ∈ ℕ) ∈ A_2^ℕ défini par q_(2i) = a et q_(2i + 1) = b pour tout i ∈ ℕ.

Question 2.4.

Soit G = (A, f, u_0) un DOL-système tel que le langage associé L(G) est infini. Montrer que G engendre un mot infini si et seulement si u_0 est préfixe de f(u_0).

Question 2.5.

Donner un D0L-système K_1 tel que S(K_1) = (u_0, u_1, u_2, …) avec u_0 ≠ ε, u_1 ≠ ε, u_2 ≠ ε et u_3 = ε. Que vaut L(K_1) ? Est-ce que K_1 engendre un mot infini?

Question 2.6.

Donner un D0L-système K_2 tel que S(K_2) = (u_0, u_1, u_2, …) avec u_0 préfixe de u_1, u_0 ≠ u_1, u_1 ≠ u_2 mais u_2 = u_3. Que vaut L(K_2) ? Est-ce que K_2 engendre un mot infini?

Question 2.7.

Donner un DOL-système K_3 tel que L(K_3) est infini mais n'engendre pas de mot infini.
Soit f : A^∗ → A^∗ un morphisme, et x ∈ A une lettre. On dit que x est une lettre mortelle (pour f ) s'il existe un entier n ≥ 1 tel que f^n(x) = ε, et que x est une lettre immortelle dans le cas contraire.

Question 2.8.

Quelles sont les lettres immortelles dans l'exemple K_2 de la question 2.6 ? Montrer que si G = (A, f, u_0) est un D0L-système tel que f(u_0) = u_0 v avec v ∈ A^∗, alors L(G) est infini si et seulement si le mot v contient une lettre immortelle pour f.

Question 2.9.

L'algorithme suivant prend en entrée un alphabet A et un morphisme f : A^∗ → A^∗, et retourne l'ensemble des lettres mortelles pour f. Si w ∈ A^∗ est un mot, on note w[i] la lettre de rang i de w, de sorte que w = w[0]w[1]…w[|w| − 1].
Lettres-mortelles ( $A, f$ )
    $T \leftarrow \emptyset$
    $M \leftarrow \emptyset$
    pour tout $x \in A$ faire
        pour tout $y \in A$ faire
            $N[x, y] \leftarrow 0$
    pour tout $y \in A$ faire
        $w \leftarrow f(y)$
        pour $i$ de 0 à $|w|-1$ faire
            $N[w[i], y] \leftarrow N[w[i], y]+1$
        $L[y] \leftarrow|w|$
        si $L[y]=0$
            alors $T \leftarrow T \cup\{y\}$
    tant que $T \neq \emptyset$ faire
        choisir $x \in T$
        $T \leftarrow T \backslash\{x\}$
        $M \leftarrow M \cup\{x\}$
        pour tout $y \in A \backslash(M \cup T)$ faire
            $L[y] \leftarrow L[y]-N[x, y]$
            si $L[y]=0$
                alors $T \leftarrow T \cup\{y\}$
    retourner $M$
Justifier la validité de cet algorithme (on précisera notamment la signification de la matrice N ). Montrer que sa complexité est O(k^2 + m), où k = Card(A) et m = ∑_(x ∈ A)|f(x)|.

Question 2.10.

Proposer et justifier un algorithme prenant en entrée un D0L-système G et un entier ℓ, retournant le préfixe de longueur ℓ de W(G) si G engendre un mot infini, et retournant « G n'engendre pas de mot infini » sinon.
Soit f : A^∗ → B^∗ un morphisme non-effaçant. Étant donné un mot infini y ∈ A^ℕ, le langage {f(w) : w préfixe de y} engendre un unique mot infini, que l'on notera f(y). On prolonge ainsi f en une application de A^ℕ dans B^ℕ.
Soit f : A^∗ → A^∗ un morphisme non-effaçant et y ∈ A^ℕ un mot infini. On dit que y est un point fixe non trivial de f si y = f(y) et s'il existe une lettre x ∈ A qui apparaît dans y et telle que f(x) ≠ x.

Question 2.11.

Soit ζ = (a ↦ ab, b ↦ ab). Donner un point fixe non trivial de ζ. Le morphisme ζ a-t-il un autre point fixe non trivial?

Question 2.12.

Soit η = (a ↦ aba, b ↦ b). Donner deux points fixes non triviaux de η. Le morphisme η a-t-il d'autres points fixes non triviaux?

Question 2.13.

Montrer que si y est point fixe non trivial d'un morphisme non-effaçant f : A^∗ → A^∗, alors y est engendré par un DOL-système que l'on précisera. En déduire que si f(x) ≠ x pour tout x ∈ A, f a au plus Card(A) points fixes non triviaux.
On dit qu'un mot infini y = (y_i)_(i ∈ ℕ) est ultimement périodique s'il existe des entiers i_0 ≥ 0 et p ≥ 1 tels que pour tout i ≥ i_0, y_i = y_(i + p).

Question 2.14.

Parmi les exemples de D0L-systèmes déjà construits, en donner un qui engendre un mot infini ultimement périodique. Montrer que tout mot infini ultimement périodique peut être engendré par un HD0L-système.

Question 2.15.

Soit T = (A_2, θ, a) le D0L-système défini à la question 1.3. Montrer que T engendre un mot infini t = W(T) = (t_i)_(i ∈ ℕ). Comment calculer t_i en fonction de i, sans calculer tous les termes précédents comme le fait l'algorithme de la question 2.10 ? Montrer que t n'est pas ultimement périodique.
Le mot infini t est appelé mot infini de Thue-Morse.

Question 2.16.

Soient μ = (a ↦ abc, b ↦ ac, c ↦ b) et ψ = (a ↦ abb, b ↦ ab, c ↦ a). Montrer que le HDOL-système T^′ = (A_3, μ, a, A_2, ψ) engendre aussi le mot infini de Thue-Morse.

Question 2.17.

Soit G = (A, f, u_0) un DoL-système. Pour n entier strictement positif, on note G_n = (A, f^n, u_0). Montrer que si G_m et G_n engendrent des mots infinis, alors W(G_m) = W(G_n).

3 Hiérarchie

Soit G = (A, f, u_0) un D0L-système. Si f est non-effaçant, on dit que G est un PD0Lsystème.
Soit H = (B, f, u_0, A, g) un HD0L-système. Si g est non-effaçant, on dit que H est un ND0L-système. Si g est lettre-à-lettre, on dit que H est un CD0L-système.
On peut également combiner ces deux notations. Si f est non-effaçant, on dit que H est un HPD0L-système. Si f et g sont non-effaçants, on dit que H est un NPD0L-système. Si f est non-effaçant et g lettre-à-lettre, on dit que H est un CPD0L-système.
On a ainsi défini huit types de L-systèmes. Pour chaque type X, on note W_A(X) l'ensemble des mots infinis sur A engendrés par un X-système. Les huit classes de mots infinis ainsi définies vérifient de manière évidente les inclusions suivantes :
W_A(D0 L), ⊂, W_A(CD0 L), ⊂, W_A(ND0 L), ⊂, W_A(HD0 L); ∪, ∪, ∪, ∪; W_A(PD0 L), ⊂, W_A(CPD0 L), ⊂, W_A(NPD0 L), ⊂, W_A(HPD0 L)
Le but de cette partie est de voir lesquelles de ces inclusions sont strictes.
Dans les questions 3.1 et 3.2 , on utilisera la propriété suivante, qui sera démontrée dans la partie 4 :
Proposition 1. Le mot infini de Thue-Morse t = W(A_2, (a ↦ ab, b ↦ ba), a) (voir les questions 1.3 et 2.15) ne contient aucun facteur de la forme vvv, avec v ∈ A_2^+.

Question 3.1.

Soit le D0L-système J_1 = (A_3, (a ↦ abccc, b ↦ baccc, c ↦ ε), a). Montrer que W(J_1) ∉ W_(A_3) (PD0L). Est-il possible de construire un tel contre-exemple sur l'alphabet A_2 ?
Indication : observer d'abord qu'en effaçant les c dans W(J_1), on retrouve le mot infini de Thue-Morse t, puis que si W(J_1) était engendré par un PD0L-système ( A_3, f, u_0 ), on aurait nécessairement f(c) = c.

Question 3.2.

Soit le NPD0L-système J_2 = (A_2, θ, a, A_2, φ), où θ = (a ↦ ab, b ↦ ba) et φ = (a ↦ aa, b ↦ bb). Montrer que φ(t) = W(J_2) ∉ W_(A_2)(DOL).
Indication : montrer que si φ(t) était engendré par un D0L-système (A_2, f, u_0), alors il contiendrait un mot de la forme vvvv avec |v| ≥ 2.

Question 3.3.

Montrer que W_A(D0L) ⊂ W_A(NPD0L). En déduire que W_A(ND0L) = W_A(NPD0L) et W_A(HD0L) = W_A(HPD0L).
Indication : on pourra procéder par récurrence sur la taille de l'alphabet, et montrer que si y = W(A, f, u_0) avec f effaçant, alors il existe un alphabet B de cardinal strictement inférieur à celui de A et des morphismes g : A^∗ → B^∗ et h : B^∗ → A^∗ tels que y = W(B, g ∘ h, g(u_0), A, h).

Question 3.4.

Montrer que W_A(HPD0L) ⊂ W_A(NPD0L).
Indication : on pourra commencer par montrer que, pour tout morphisme f : B^∗ → B^∗, il existe un entier strictement positif N tel que pour tout x ∈ B, Alph(f^N(x)) = Alph(f^(2N)(x)), puis utiliser la question 2.17 pour se ramener à un HPD0L-système H~ = (B, f~, u_0, A, g~) tel que g~(f~(x)) = ε si et seulement si g~(x) = ε.

Question 3.5.

Montrer que W_A( NPD0L ) ⊂ W_A( CPD0L ). Illustrer cette inclusion en construisant un CPD0L-système engendrant le mot infini φ(t) construit à la question 3.2.
Indication : si H = (B, f, u_0, A, g) est le NPD0L-système de départ, on pourra, après avoir modifié f et g, utiliser l'alphabet intermédiaire B~ = {(x, i) : x ∈ B, 1 ≤ i ≤ |g(x)|}.

Question 3.6.

En rassemblant les résultats de cette partie, conclure en précisant la nature (inclusion stricte ou égalité) de toutes les inclusions figurant dans le diagramme (1). On distinguera les cas où Card(A) vaut 1, 2, ou au moins 3.

4 Mots sans carré, mots sans cube

Soit w un mot fini ou infini. On dit que w contient un carré s'il existe un mot non vide v ∈ A^+tel que vv est facteur de w (le mot vv est appelé le carré de v ). Dans le cas contraire, on dit que w est sans carré. Ainsi, abcbacbab contient un carré (le carré de cba) tandis que abcacbabc est sans carré. On note E^2(A) l'ensemble des mots de A^∗ sans carré.
De même, on dit que w est sans cube s'il ne contient aucun facteur de la forme vvv avec v ∈ A^+.

Question 4.1.

Montrer qu'il n'existe qu'un nombre fini de mots sans carré dans A_2^∗. Décrire le langage E^2(A_2).

Question 4.2.

Proposer et justifier un algorithme prenant en entrée un mot w et retournant « w contient un carré » ou « w est sans carré » selon la nature de w. Quelle est sa complexité?

Question 4.3.

Proposer et justifier un algorithme prenant en entrée l'alphabet A et un entier ℓ, et retournant la liste des mots sans carré de longueur inférieure ou égale à ℓ dans A^∗. La complexité devra être au plus en O(kℓ^2 m), où k = Card(A) et m est le nombre de mots sans carré retournés.
On pourra utiliser le fait qu'un mot w est sans carré si et seulement si w n'a aucun suffixe de la forme vv et son préfixe de longueur |w| − 1 est sans carré.
Dans les questions qui suivent, on cherche à montrer que E^2(A_3) est infini. On considère pour cela le morphisme μ = (a ↦ abc, b ↦ ac, c ↦ b).

Question 4.4.

Montrer que μ est injectif.
On note V l'ensemble des mots de A_3^∗ qui ne contiennent ni aa, ni bb, ni cc, ni aba, ni cbc comme facteurs.

Question 4.5.

Montrer que pour tout mot w ∈ V, μ(w) ∈ V.

Question 4.6.

Montrer que pour tout mot w ∈ A_3^∗ et tout facteur v de μ(w) autre que ε ou b, il existe un unique triplet ( x, y, z ), où x ∈ {ε, c, bc}, y ∈ A_3^∗ et z ∈ {ε, a, ab} tel que v = xμ(y)z. Montrer que le mot y est alors facteur de w.

Question 4.7.

Montrer que, si w ∈ A_3^∗ et μ(w) contient un carré, alors w contient soit un carré, soit un mot de la forme aybya avec y ∈ A_3^∗.
Indication : si μ(w) contient vv, commencer par appliquer le résultat de la question 4.6 à v.

Question 4.8.

Montrer qu'aucun mot de V ne contient de facteur de la forme aybya.

Question 4.9.

Déduire de ce qui précède que μ(V ∩ E^2(A_3)) ⊂ V ∩ E^2(A_3). Construire un DOL-système G tel que L(G) est infini et L(G) ⊂ E^2(A_3).
Un mot sans carré w ∈ E^2(A_3) est dit indéfiniment prolongeable si pour tout ℓ, il existe u et v dans A_3^∗ de longueur ℓ tels que uwv soit sans carré. Un mot sans carré est dit non prolongeable si pour toute lettre x ∈ A_3, xw et wx contiennent chacun un carré.

Question 4.10.

Montrer qu'il existe dans A_3^∗ une infinité de mots sans carré indéfiniment prolongeables, et une infinité de mots sans carré non prolongeables (on commencera par contruire un mot sans carré non prolongeable).

Question 4.11.

En utilisant le résultat de la question 2.16, montrer que le mot infini de Thue-Morse t est sans cube.

Questions fréquentes

4 questions
Sur quels chapitres porte ce sujet d'informatique des ENS MP 2001 ?
Afficher ou masquer la section

Sur quels chapitres porte ce sujet d'informatique des ENS MP 2001 ?

Il porte sur les mots et morphismes de monoïdes, les langages formels et automates, ainsi que sur des algorithmes de manipulation de mots (détection de carrés) et leur analyse de complexité.

Les parties de ce sujet sont-elles indépendantes ?

L'énoncé précise que la partie 4, sur les mots sans carré et sans cube, est largement indépendante des parties précédentes, bien qu'elle réutilise le mot de Thue-Morse introduit en partie 2.

Qu'est-ce qu'un L-système, étudié dans ce sujet ?

C'est un système fondé sur un morphisme de mots itéré, introduit par Lindenmayer pour modéliser la croissance d'organismes vivants, et utilisé ici pour engendrer des mots infinis comme le mot de Thue-Morse.

Ce sujet demande-t-il de proposer des algorithmes ?

Oui, plusieurs questions demandent de proposer et justifier des algorithmes, notamment pour détecter les lettres mortelles d'un morphisme ou reconnaître les mots sans carré, avec analyse de leur complexité.

Pas de description pour le moment