Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter

Feuille d'exercices 1

Mots et langages

Préfixes, facteurs et sous-mots, produits et étoiles de langages, et quelques identités à démontrer ou à réfuter. Chapitre 1.

Sauf mention contraire, $\Sigma = \{a, b\}$.

Corrigé
  1. Préfixes : $\varepsilon, a, ab, aba, abab$. Suffixes : $\varepsilon, b, ab, bab, abab$. Facteurs : $\varepsilon, a, b, ab, ba, aba, bab, abab$ (huit ; $ab$ apparaît deux fois dans $u$ mais ne compte qu'une fois).
  2. $\varepsilon$ ; $a, b$ ; $aa, ab, ba, bb$ ; $aab, aba, abb, bab$ ; $abab$. Douze sous-mots. Les mots de longueur 3 manquants ($aaa$, $baa$…) demanderaient trois $a$, ou un $b$ avant deux $a$.
  3. Oui pour les préfixes : un par longueur, de 0 à $n$. Non pour les sous-mots : il y a $2^n$ façons de choisir les lettres à garder, mais des choix différents peuvent donner le même mot (ici, 12 sous-mots pour $2^4 = 16$ choix). Dès qu'une lettre apparaît deux fois, garder l'une ou l'autre de ses occurrences donne le même sous-mot : on a exactement $2^n$ sous-mots si et seulement si les lettres du mot sont toutes différentes. Sur $\{a, b\}$, cela n'arrive que pour $n \leq 2$ ($ab$ a bien 4 sous-mots).
Corrigé
  1. $L_1 L_2 = \{a, ab, abb\}$ ; $L_2 L_1 = \{a, ab, ba, bab\}$ ; $L_1^2 = \{aa, aab, aba, abab\}$.
  2. Trois mots : $ab$ s'obtient deux fois, comme $a \cdot b$ et comme $ab \cdot \varepsilon$. Le produit est un ensemble, les doublons disparaissent.
  3. $abab = ab \cdot ab$ : oui. $aba = ab \cdot a$ : oui. $abba$ : non. Chaque mot de $L_1$ commence par $a$, donc chaque $b$ d'un mot de $L_1^*$ est précédé d'un $a$ ou fait partie de $ab$ ; $bb$ ne peut apparaître.
Corrigé
  1. Faux : $L \cdot \emptyset = \emptyset$ ($\emptyset$ est absorbant). Contre-exemple : $L = \{a\}$.
  2. Vrai : $u\varepsilon = u$ pour tout $u$.
  3. Vrai. $L^* \subseteq L^*L^*$ (prendre $\varepsilon$ dans le second facteur) ; et deux suites de mots de $L$ mises bout à bout en forment une, donc $L^*L^* \subseteq L^*$.
  4. Faux : $L_1 = \{a\}$, $L_2 = \{b\}$. $abab \in (L_1L_2)^*$ mais pas dans $a^*b^*$ ; et $aab \in a^*b^*$ mais pas dans $(ab)^*$.
  5. Faux : avec les mêmes, $ab \in \{a, b\}^*$ mais $ab \notin a^* \cup b^*$.
  6. Vrai : un découpage en mots de $L_1$ est un découpage en mots de $L_2$.
  7. Faux en général : si $\varepsilon \in L$, alors $\varepsilon \in L^+$. Contre-exemple : $L = \{\varepsilon\}$, $L^+ = \{\varepsilon\}$ et $L^* \setminus \{\varepsilon\} = \emptyset$. C'est vrai si $\varepsilon \notin L$.
Corrigé
  1. Les mots qui contiennent au moins un $a$.
  2. Les mots qui contiennent un nombre pair de $a$ : des $b$, puis des blocs de deux $a$ séparés et suivis de $b$.
  3. Les mots qui ne contiennent pas le facteur $aa$ : chaque $a$ est suivi d'un $b$, sauf éventuellement un $a$ final.
  4. Les mots de longueur paire.
Corrigé
  1. $f(0) = 1$ ($\varepsilon$), $f(1) = 2$, $f(2) = 3$ ($ab$, $ba$, $bb$), $f(3) = 5$ ($aba$, $abb$, $bab$, $bba$, $bbb$).
  2. Un mot de longueur $n \geq 2$ sans $aa$ commence soit par $b$, suivi de n'importe quel mot sans $aa$ de longueur $n - 1$ ; soit par $a$, et alors la lettre suivante est forcément $b$, suivie de n'importe quel mot sans $aa$ de longueur $n - 2$. Les deux cas sont disjoints.
  3. $f(4) = 8$, $f(5) = 13$, $f(6) = 21$. C'est la suite de Fibonacci, décalée.