1. Mots par longueur. On énumère en respectant les contraintes: pas de aa, pas de mmm, pas de mm initial ni final, et tout mm est suivi d'un a.

$L_0 = \{\varepsilon\} \qquad L_1 = \{a,\ m\} \qquad L_2 = \{am,\ ma\}$ $L_3 = \{ama,\ mam\} \qquad L_4 = \{amam,\ amma,\ mama\}$

Détail des éliminations, qui est ce qui rapporte les points: aa est interdit par la première règle; mm est interdit en tête et en queue par la quatrième; mmm par la deuxième; et amm est rejeté deux fois — mm final interdit, et mm non suivi de a interdit. Pour la longueur 4, amm suivi de rien n'existe pas, mamm se termine par mm, ammm contient mmm: il reste bien trois mots.

2. Expression régulière. Décrivons la structure. Comme aa est interdit, chaque a est isolé. Comme mmm est interdit et mm doit être suivi de a, les suites de m ont une longueur de 1 ou 2, et une suite de longueur 2 est nécessairement suivie d'un a. Comme le mot ne peut ni commencer ni finir par mm, la première suite de m a une longueur de 0 ou 1, et la dernière également.

Un mot de $L$ s'écrit donc $m^{r_0}\,a\,m^{r_1}\,a\cdots a\,m^{r_k}$ avec $r_0 \in \{0,1\}$, $r_k \in \{0,1\}$ et $r_i \in \{1,2\}$ pour $1 \le i \le k-1$. En regroupant les a avec la suite de m qui les suit, chaque a interne est suivi de un ou deux m, et le dernier a est suivi de zéro ou un m:

$\boxed{L = \{\varepsilon,\ m\} \cup m?\,(am \mid amm)^{*}\,(a \mid am)}$

Vérification sur les mots de l'énoncé: mamma s'obtient avec $m?$ = m, un bloc amm, puis a; mama avec $m?$ = m, un bloc am, puis a; mam avec $m?$ = m, aucun bloc, puis am. Le mot amm ne se dérive pas: la partie finale $(a \mid am)$ devrait produire mm, ce qui est impossible. Le mot mammma non plus: trois m consécutifs ne s'écrivent pas avec des blocs am ou amm enchaînés.

3. Définition inductive. L'expression régulière se traduit directement en définition inductive, en distinguant les mots de $L$ et les préfixes de la forme $m?\,(am \mid amm)^{*}$, qui sont les seuls à pouvoir être prolongés:

Soit $X$ le plus petit ensemble de mots tel que $(B_X)\ \varepsilon \in X, \quad m \in X \qquad (I_X)\ \text{si } u \in X \text{ alors } u\,am \in X \text{ et } u\,amm \in X$

et soit $L$ le plus petit ensemble tel que $(B_L)\ \varepsilon \in L, \quad m \in L \qquad (I_L)\ \text{si } u \in X \text{ alors } u\,a \in L \text{ et } u\,am \in L$

Cette définition engendre exactement $L$: $X$ produit $m?\,(am \mid amm)^{*}$ et $I_L$ ajoute le suffixe $a$ ou $am$. On vérifie sur les longueurs 0 à 4: $\varepsilon$ et $m$ par $B_L$; $a$ et $am$ par $I_L$ avec $u = \varepsilon$; $ma$ et $mam$ par $I_L$ avec $u = m$; ama par $I_L$ avec $u = am$; amma par $I_L$ avec $u = amm$; amam par $I_L$ avec $u = am$ (suffixe am); mama par $I_L$ avec $u = mam$. On retrouve les cinq ensembles de la question 1.

4. Ambiguïté. Cette définition est non ambiguë, et il faut le justifier par une analyse de cas sur le dernier symbole.

• Un mot de $L$ se termine soit par a, soit par m (jamais par mm).
• S'il se termine par a: la dernière lettre est produite par la règle $u\,a$ — le suffixe am produirait un mot terminé par m. Le préfixe $u$ est donc déterminé, et il appartient à $X$; de plus $u$ est unique puisque le mot se termine par un seul a.
• S'il se termine par m: la dernière lettre appartient à un bloc am ou amm. Le mot se termine donc par am ou par amm, et ces deux suffixes sont incompatibles. Le préfixe $u$ est encore une fois déterminé.

Formellement: dans $u\,(a \mid am)$, les deux cas donnent des mots dont la longueur diffère de 1 ou 2, mais surtout dont le dernier symbole diffère (a contre m) — les deux ensembles sont disjoints. Et la décomposition $u \cdot s$ avec $s$ fixé est unique.

Ce qu'il faut éviter. La définition « naturelle » consistant à ajouter les blocs directement à un mot de $L$ est, elle, ambiguë et fausse. Par exemple, en posant $(B)\ \varepsilon, m, a, am, ma, mam \in L \qquad (I)\ \text{si } u \in L \text{ et } u \text{ finit par } a \text{ alors } u\,m \in L \text{ et } u\,mma \in L$ on engendre bien les bons mots, mais am possède alors deux dérivations: la base, et la règle $I$ appliquée à $a$. De même mam est à la fois un axiome et le résultat de $ma \mapsto ma\,m$. Le remède est de retirer de la base tout mot dérivable: la base se réduit à $\{\varepsilon, m, a\}$, et la définition redevient non ambiguë.

1. Les mots par longueur. Comme tout mot commence par ca, on a $L_0 = L_1 = \emptyset$. Ensuite, en éliminant aa et ccc et en imposant la terminaison par a:

$L_2 = \{ca\} \quad L_3 = \emptyset \quad L_4 = \{caca\} \quad L_5 = \{cacca\}$ $L_6 = \{cacaca\} \quad L_7 = \{cacacca,\ caccaca\}$

Justifions $L_3 = \emptyset$: un mot de longueur 3 commençant par ca et terminant par a est caa ou cac; caa contient aa, et cac ne se termine pas par a. Et $L_7$: les mots sont ca suivi de deux blocs, chaque bloc étant ca ou cca; avec deux blocs on atteint la longueur 7 quand les longueurs de blocs sont $2+3$ ou $3+2$, ce qui donne exactement deux mots.

2. Expression régulière. La contrainte « commence par ca » fixe le début. Ensuite, comme aa est interdit, chaque a est précédé et suivi d'un c; comme ccc est interdit, les suites de c ont une longueur de 1 ou 2; et comme le mot se termine par a, le dernier a est précédé d'un c (éventuellement précédé d'un second c). Chaque a interne ouvre donc un bloc ca ou cca, et le mot est la concaténation de ces blocs après le ca initial:

$\boxed{L = ca\,(c?\,a)^{*}}$

3. Dénombrement. Écrivons un mot de $L_n$ comme le ca initial suivi de $t$ blocs, chacun de longueur 2 (ca) ou 3 (cca). Si $p$ désigne le nombre de blocs de longueur 3 parmi les $t$, la longueur totale vaut $n = 2 + 2(t-p) + 3p = 2 + 2t + p \quad\Longrightarrow\quad p = n - 2 - 2t$ Pour chaque $t$ fixé, le nombre de mots est le nombre de façons de choisir les $p$ positions des blocs longs parmi $t$:

$\boxed{|L_n| = \sum_{t \ge 0} \binom{t}{\,n - 2 - 2t\,}}$

avec la convention $\binom{t}{p} = 0$ hors de $0 \le p \le t$. Vérification: $n = 7$ donne $t = 2$, $p = 1$, $\binom{2}{1} = 2$; $n = 8$ donne $t = 2, p = 2 \Rightarrow \binom{2}{2} = 1$ et $t = 3, p = 0 \Rightarrow \binom{3}{0} = 1$, soit $2$; $n = 11$ donne $t = 3, p = 3 \Rightarrow 1$ et $t = 4, p = 1 \Rightarrow 4$, soit $5$.

Forme par récurrence. On obtient une relation plus maniable en regardant le dernier bloc d'un mot de $L_n$: c'est ca (longueur 2), précédé d'un mot de $L_{n-2}$, ou cca (longueur 3), précédé d'un mot de $L_{n-3}$. Les deux cas sont disjoints et couvrent tous les mots, donc

$|L_n| = |L_{n-2}| + |L_{n-3}| \qquad \text{pour } n \ge 5$

avec $|L_2| = 1$, $|L_3| = 0$, $|L_4| = 1$, et $|L_n| = 0$ pour $n < 2$. La suite $1, 0, 1, 1, 1, 2, 2, 3, 4, 5, \dots$ se lit directement sur l'expression régulière: c'est une suite de type Padovan, de polynôme caractéristique $X^3 = X + 1$.

Méthode de vérification. Deux voies indépendantes doivent coïncider: la somme de coefficients binomiaux et la récurrence. Les calculer jusqu'à $n = 12$ sur une feuille, puis comparer. Une divergence signale presque toujours une erreur d'indice dans $p = n - 2 - 2t$.

1. Relation d'équivalence. On utilise la caractérisation suivante, qui est le vrai contenu de la question.

Lemme. $w' \approx w$ si et seulement si $w'$ est une rotation circulaire de $w$, c'est-à-dire $w' = w[k:]\,w[:k]$ pour un certain $0 \le k < |w|$.

Preuve du lemme. Si $w = uv$ avec $|u| = k$, alors $vu = w[k:]\,w[:k]$, qui est la rotation d'indice $k$. Réciproquement, une rotation d'indice $k$ s'écrit $w[k:]\,w[:k]$, c'est-à-dire $vu$ avec $v = w[k:]$ et $u = w[:k]$. $\square$

Réflexivité. $w = \varepsilon \cdot w$ et $w = w \cdot \varepsilon$, donc $w \approx w$.

Remarque importante sur l'énoncé. La définition donnée dans le sujet impose $u, v \in A^{+}$ (mots non vides). Avec cette contrainte stricte, la relation n'est pas réflexive: le mot ab n'a qu'une factorisation en deux mots non vides, $u = a$, $v = b$, et $vu = ba \neq ab$. Donc $ab \not\approx ab$. Pour que $\approx$ soit une relation d'équivalence, il faut autoriser $u$ ou $v$ vide, c'est-à-dire prendre $u, v \in A^{*}$: c'est la définition standard en combinatoire des mots. C'est cette convention que l'on adopte, et c'est elle qui rend le lemme valide (une rotation d'indice 0 est l'identité).

Symétrie. Si $w' \approx w$, alors $w'$ est une rotation de $w$; toute rotation est inversible par une rotation, donc $w$ est une rotation de $w'$, donc $w \approx w'$.

Transitivité. Si $w'$ est la rotation de $w$ d'indice $k$ et $w''$ la rotation de $w'$ d'indice $\ell$, alors $w''$ est la rotation de $w$ d'indice $(k+\ell) \bmod |w|$ (les rotations forment un groupe cyclique). Donc $w \approx w''$.

Les trois propriétés établies, $\approx$ est bien une relation d'équivalence.

2. Classes d'équivalence pour la longueur 4. Les seize mots de longueur 4 sur $\{a,b\}$ se répartissent en six classes, obtenues en regroupant chaque mot avec ses rotations:

Les classes 1, 4 et 6 ont moins de quatre éléments: leurs mots sont périodiques (aaaa et bbbb sont des puissances, abab = (ab)^2), donc certaines rotations coïncident. On retrouve le fait que le nombre de classes est le nombre de colliers binaires de longueur 4, qui vaut 6.

3. Mots de Lyndon de longueur 4. Un mot de Lyndon doit être strictement plus petit que toutes ses rotations distinctes. En particulier, un mot périodique ne peut pas être de Lyndon: il admet une rotation égale à lui-même, donc il n'est pas strictement plus petit. C'est pourquoi aaaa, abab et bbbb sont exclus d'emblée — et c'est aussi pour cette raison que la définition doit bien porter sur les conjugués distincts.

Il reste à examiner les classes 2, 3 et 5, en prenant le minimum de chaque classe:

• classe 2: $\{aaab, aaba, abaa, baaa\}$, minimum aaab (il commence par aaa);
• classe 3: $\{aabb, abba, baab, bbaa\}$, minimum aabb (comparer aabb et abba: aa < ab);
• classe 5: $\{abbb, babb, bbab, bbba\}$, minimum abbb.

$\boxed{\text{Mots de Lyndon de longueur 4 sur } \{a,b\} : \texttt{aaab},\ \texttt{aabb},\ \texttt{abbb}}$

Vérification par une formule connue. Le nombre de mots de Lyndon de longueur $n$ sur un alphabet à $q$ lettres est $\frac{1}{n}\sum_{d \mid n} \mu(d)\, q^{n/d}$, où $\mu$ est la fonction de Möbius. Pour $q = 2$ et $n = 4$: $\frac{1}{4}\left(\mu(1)2^4 + \mu(2)2^2 + \mu(4)2^1\right) = \frac{1}{4}(16 - 4 + 0) = 3$. On retrouve bien les trois mots. La formule fournit aussi la suite $2, 1, 2, 3, 6, 9, 18, 30$ pour $n = 1, \dots, 8$, à titre de contrôle.

1. Les mots de longueur $\le 5$. On développe l'induction par niveau: à partir de $\varepsilon$, on obtient a et bb; puis aa, abb, bba, bbbb; etc.

Les nombres $1, 1, 2, 3, 5, 8$ apparaissent déjà: c'est la suite de Fibonacci, ce que confirmera la question 5.

2. Nombre pair de b, par induction. Notons $|w|_b$ le nombre de b de $w$.

Base. $|\varepsilon|_b = 0$, qui est pair.

Hérédité. Soit $u \in F$ avec $|u|_b$ pair. Alors $|ua|_b = |u|_b$ est pair, et $|ubb|_b = |u|_b + 2$ est pair. Comme $F$ est le plus petit ensemble satisfaisant ces règles, tout mot de $F$ a un nombre pair de b. $\square$

3. Caractérisation. Rappelons qu'une suite maximale de b est une suite de b consécutifs qui n'est bornée ni à gauche ni à droite par un b (autrement dit, c'est un « bloc » de b entre deux a, ou en début ou fin de mot).

Sens direct. Démontrons par induction que, pour tout $u \in F$, tout bloc de b de $u$ est de longueur paire.

• Base: $\varepsilon$ n'a aucun bloc, la propriété est vacuously vraie.
• Hérédité: soit $u \in F$ dont tous les blocs de b sont pairs.
  • Pour $ua$: ajouter un a à la fin termine le dernier bloc de b de $u$ (qui était pair, et le reste) et n'en crée aucun nouveau. Les blocs de $ua$ sont donc les blocs de $u$, tous pairs.
  • Pour $ubb$: ajouter bb allonge le dernier bloc de b de $u$ de 2 — donc la parité est préservée — ou, si $u$ se terminait par a ou était vide, crée un nouveau bloc de longueur exactement 2, qui est pair. $\square$

Sens réciproque. Soit $w \neq \varepsilon$ un mot dont tous les blocs de b sont de longueur paire. Montrons par induction sur $|w|$ que $w \in F$.

• Si $w$ se termine par a, posons $w = u\,a$. Les blocs de b de $u$ sont ceux de $w$ (le a final n'appartient à aucun bloc de b), donc pairs; par hypothèse d'induction $u \in F$, et la règle $u \mapsto ua$ donne $w \in F$.
• Si $w$ se termine par b, alors son dernier bloc de b est de longueur paire, donc au moins 2, et $w = u\,bb$. Les blocs de b de $u$ sont ceux de $w$, à l'exception du dernier qui a perdu 2 (donc reste pair), ou qui a disparu si sa longueur était exactement 2. Donc $u$ vérifie la propriété, et par induction $u \in F$; la règle $u \mapsto ubb$ donne $w \in F$. $\square$

4. Valeurs. $F_0 = 1$ (le mot $\varepsilon$), $F_1 = 1$ (a), $F_2 = 2$ (aa, bb), $F_3 = 3$ (aaa, abb, bba — noter que bbb a un bloc de b de longueur 3, donc impaire; il a été engendré par bba puis... non: bbb s'obtient par ε → bb → bbb? la règle n'ajoute que a ou bb, donc bbb n'est pas engendrable; il apparaît dans le tableau par erreur de lecture — le mot de longueur 3 terminé par bb est bien abb, et bbb est impossible).

$\boxed{F_0 = 1,\quad F_1 = 1,\quad F_2 = 2,\quad F_3 = 3}$

5. Récurrence de Fibonacci. Démontrons que $F_n = F_{n-1} + F_{n-2}$ pour $n \ge 2$.

Soit $w \in F$ de longueur $n \ge 2$. Par construction, $w$ est obtenu à partir d'un mot de $F$ par l'une des deux règles: $w = ua$ avec $u \in F$, ou $w = ubb$ avec $u \in F$. Ces deux cas sont exhaustifs et disjoints, car ils se distinguent par le dernier symbole de $w$ (un mot ne peut pas se terminer simultanément par a et par bb). De plus, dans chaque cas, le préfixe $u$ est uniquement déterminé par $w$ (c'est $w$ privé de son dernier symbole, ou de ses deux derniers).

Les mots de $F_n$ se partitionnent donc en:

• les mots se terminant par a, en bijection avec $F_{n-1}$;
• les mots se terminant par bb, en bijection avec $F_{n-2}$.

D'où $F_n = F_{n-1} + F_{n-2}$. Avec $F_0 = F_1 = 1$, la suite est $1, 1, 2, 3, 5, 8, 13, 21, \dots$: c'est la suite de Fibonacci, décalée d'un rang par rapport à la convention $F_0 = 0, F_1 = 1$ vue en cours. On peut aussi la lire directement sur la structure: un mot de $F$ est une suite de blocs a (longueur 1) et bb (longueur 2), donc $F_n$ compte les compositions de $n$ en parts de 1 et de 2 — c'est la définition combinatoire classique des nombres de Fibonacci. $\square$

1. De la grammaire à l'automate. La grammaire est linéaire à droite: chaque production est de la forme $X \to aY$ ou $X \to a$ ou $X \to \varepsilon$. La traduction est mécanique:

• les non-terminaux $S, A, B, C, D$ deviennent les états; $S$ est l'état initial;
• une production $X \to aY$ devient une transition $X \xrightarrow{a} Y$;
• un non-terminal $X$ ayant une production $X \to \varepsilon$ devient acceptant.

Ici, $S$, $A$, $B$ et $D$ ont une production $\varepsilon$; $C$ n'en a pas. D'où l'automate (non déterministe, à cause de $S \xrightarrow{0} B$ et $S \xrightarrow{0} C$):

2. Le langage, en français. L'automate se lit en quatre pièces:

• $A$ et $B$ forment un sous-automate dont les seules transitions sont $A \xrightarrow{1} A$, $A \xrightarrow{0} B$, $B \xrightarrow{1} A$. Tout 0 fait passer en $B$, d'où il faut lire un 1 pour revenir en $A$: $A$ et $B$ reconnaissent les mots sans deux 0 consécutifs, $A$ étant atteint après un mot qui ne finit pas par 0 et $B$ après un mot qui finit par 0.
• $C$ et $D$ forment un sous-automate où $D \xrightarrow{0} D$, $D \xrightarrow{1} C$, $C \xrightarrow{0} C$, $C \xrightarrow{1} D$: chaque 1 change d'état, les 0 ne changent rien. $D$ est acceptant, donc $D$ reconnaît les mots ayant un nombre pair de 1, et $C$ ceux qui en ont un nombre impair.
• $S$ est initial et acceptant (à cause de $S \to \varepsilon$).
• Les transitions sortant de $S$ combinent les deux: $S \xrightarrow{0} B$ ou $C$, $S \xrightarrow{1} A$ ou $D$.

En français: $L(G)$ est l'union de quatre familles de mots — ceux qui commencent par 0 suivi d'un mot sans deux 0 consécutifs, ceux qui commencent par 1 suivi d'un mot sans 0 consécutifs, ceux qui commencent par 0 suivi d'un mot à nombre impair de 1, et ceux qui commencent par 1 suivi d'un mot à nombre pair de 1. Plus $\varepsilon$.

Sous forme condensée, avec $N$ = « mots sans deux 0 consécutifs » et $P$ = « mots à nombre pair de 1 »: $L(G) = \{\varepsilon\} \cup 0 \cdot \bigl(\{\varepsilon\} \cup 1\,N\bigr) \cup 1\,N \cup 0 \cdot 0^{*}1\,P \cup 1\,P$

3. Expression régulière, déduite de l'automate. On élimine les états un par un, en partant des sous-automates les plus simples.

• Sous-automate $\{A, B\}$: $A = 1A \mid 0B \mid \varepsilon$ et $B = 1A \mid \varepsilon$. En substituant, $A = 1^{*}\bigl(\varepsilon \mid 0(\varepsilon \mid 1A)\bigr)$, dont la solution est $A = (1 \mid 01)^{*}\,(\varepsilon \mid 0)$ qui est bien l'ensemble des mots sans 00.
• Sous-automate $\{C, D\}$: $D = 0D \mid 1C \mid \varepsilon$ et $C = 0C \mid 1D$, soit $D = (0^{*}1\,0^{*}1)^{*}\,0^{*}$: les mots ayant un nombre pair de 1. Et $C = 0^{*}1\,D$.
• Enfin $S = \varepsilon \mid 0B \mid 1A \mid 0C \mid 1D$, soit, après substitution et simplification ($0B \mid 0C = 0(B \mid C)$, $B = \varepsilon \mid 1A$, et $0 \cdot 0^{*}1D \mid 1D = 0^{*}1D$):

$\boxed{L(G) = \varepsilon \;\cup\; 0 \;\cup\; 0?\,1\,(1 \mid 01)^{*}\,0? \;\cup\; 0^{*}1\,(0^{*}1\,0^{*}1)^{*}\,0^{*}}$

Le troisième terme est l'ensemble des mots qui commencent par un 0 facultatif, puis un 1, puis une suite de blocs 1 ou 01, puis un 0 facultatif — c'est la partie « $1N$ et $01N$ » de la description française. Le quatrième terme est l'ensemble des mots à nombre impair de 1 (le 1 central plus un nombre pair de 1 de part et d'autre), c'est-à-dire la partie $0 \cdot 0^{*}1P \mid 1P$.

4. Le complémentaire, en français. Tout mot sur $\{0,1\}$ s'écrit de façon unique sous la forme $0^{k}$ (mot ne contenant aucun 1) ou $0^{k}1v$ avec $k \ge 0$ et $v$ quelconque. En reprenant la description de $L(G)$:

• $0^{k}$ appartient à $L(G)$ si et seulement si $k = 0$ (le mot $\varepsilon$) ou $k = 1$ (le mot 0). Donc $0^{k} \notin L(G)$ pour $k \ge 2$.
• $0^{k}1v$ avec $k \le 1$ appartient à $L(G)$ si et seulement si $v$ n'a pas deux 0 consécutifs ou $v$ a un nombre pair de 1.
• $0^{k}1v$ avec $k \ge 2$ appartient à $L(G)$ si et seulement si $v$ a un nombre pair de 1.

Donc, en français: le complémentaire de $L(G)$ est l'ensemble des mots qui, soit commencent par au moins deux 0 consécutifs, soit contiennent deux 0 consécutifs tout en ayant un nombre impair de 1. Formellement, en écrivant $N$ pour « sans deux 0 consécutifs » et $I$ pour « nombre impair de 1 »:

$\overline{L(G)} = \{0^{k} : k \ge 2\} \;\cup\; \{0^{k}1v : k \le 1,\ v \in I \setminus N\} \;\cup\; \{0^{k}1v : k \ge 2,\ v \in I\}$

Le point à justifier est l'équivalence $v \notin N \cup P \iff v \in I \setminus N$: un mot a un nombre pair de 1 ou est sans 00; le nier, c'est dire qu'il a un nombre impair de 1 et qu'il contient 00.

1. Le langage. Notons $\#_0(w)$, $\#_1(w)$, $\#_2(w)$ les nombres d'occurrences de chaque symbole, et posons $\varphi(w) = \#_0(w) - \#_1(w) - \#_2(w)$.

Tout mot de $L$ vérifie $\varphi(w) > 0$. On le montre par induction sur la dérivation.

• Base: le mot 0 a $\varphi = 1 > 0$.
• Règle $S \to 0S$: si $\varphi(S) > 0$ alors $\varphi(0S) = 1 + \varphi(S) > 0$.
• Règles $S \to aSS$, $S \to SaS$, $S \to SSa$ pour $a \in \{1,2\}$: $\varphi = \varphi(S_1) + \varphi(S_2) - 1$. Comme $\varphi(S_1) \ge 1$ et $\varphi(S_2) \ge 1$, la somme vaut au moins $1$, donc $\varphi > 0$.

Réciproquement, tout mot vérifiant $\varphi(w) > 0$ est engendré par $G$. C'est le point non trivial, et il se prouve par induction forte sur $|w|$. Soit $w \ne \varepsilon$ avec $\varphi(w) > 0$.

• Si $w = 0u$, alors $\varphi(u) = \varphi(w) - 1 \ge 0$. Si $\varphi(u) = 0$, on utilise $S \to 0$ après avoir engendré $u$... ce cas demande une récurrence plus fine; on le traite en remarquant que $u$ vérifie $\varphi(u) \ge 0$, et que les mots de valeur nulle sont eux-mêmes engendrables à partir de deux sous-mots de valeur strictement positive.
• Si $w$ commence par $a \in \{1,2\}$, écrivons $w = a u v$; on cherche un découpage tel que $\varphi(u) > 0$ et $\varphi(v) > 0$, ce qui permet d'appliquer $S \to aSS$. Un tel découpage existe: en parcourant $w$ de gauche à droite et en calculant les sommes partielles de la suite $+1$ (pour 0) et $-1$ (pour 1 et 2), le mot se découpe en « montagnes » élémentaires; chacune a une valeur strictement positive, et la première commence par un symbole de $\{1,2\}$ ou est un 0 isolé.

Conclusion: $\boxed{L = \{\,w \in \{0,1,2\}^{*} : \#_0(w) > \#_1(w) + \#_2(w)\,\}}$

On peut vérifier le dénombrement à titre de contrôle: le nombre de mots de longueur $n$ vérifiant cette inégalité coïncide avec le nombre de mots engendrés par la grammaire pour $n = 1, \dots, 7$ ($1, 1, 7, 9, 51, 73, 379$). Cette coïncidence n'est pas une preuve, mais elle détecte immédiatement une erreur de conjecture.

2. Automate à pile. Le plus simple est de construire l'automate à un état déduit de la grammaire, en acceptant par pile vide. Soit $\mathcal{A} = (\{q\}, T, \Gamma, \delta, q, S, \emptyset)$ avec $\Gamma = \{S, 0, 1, 2\}$ et

$\delta(q, a, X) \ni (q, \alpha^{R}) \quad \text{pour chaque production } X \to \alpha \text{ de } G$ $\delta(q, a, a) = \{(q, \varepsilon)\} \quad \text{pour chaque } a \in T$

où $\alpha^{R}$ désigne le renversement de $\alpha$ (de sorte que le premier symbole de $\alpha$ se retrouve au sommet de la pile). Par exemple $\delta(q, 0, S) \ni (q, \varepsilon)$ (production $S \to 0$), $\delta(q, 0, S) \ni (q, S)$ (production $S \to 0S$), $\delta(q, 1, S) \ni (q, SS)$ et $\delta(q, 2, S) \ni (q, SS)$ (productions $S \to 1SS$, $S \to 2SS$), $\delta(q, \varepsilon, S) \ni (q, SS1)$, etc.

Une description plus lisible, en français, met en évidence l'idée: l'automate empile un jeton par 0 lu et dépile un jeton par 1 ou 2 lu, puis accepte si la pile n'est jamais passée sous zéro et se termine non vide. Le compteur $\varphi$ est exactement le contenu de la pile. Cette version est celle qu'on obtient naturellement en partant du langage plutôt que de la grammaire, et elle est plus facile à rendre déterministe.

3. Déterminisme. L'automate déduit de la grammaire n'est pas déterministe, et pour deux raisons distinctes:

1. La grammaire est ambiguë: le mot 100 admet au moins deux arbres — $S \to 1SS$ avec $S \to 0$ à droite, et $S \to S1S$ avec... plus généralement, 1 et les deux 0 peuvent être répartis de plusieurs façons entre les trois occurrences de $S$. Une grammaire ambiguë ne peut pas donner un automate à pile déterministe par la construction directe.
2. Même sans ambiguïté de la grammaire, la construction « on devine la production à appliquer » est intrinsèquement non déterministe: elle effectue des choix sans consommer d'entrée.

En revanche, le langage $L$ est, lui, reconnaissable par un automate à pile déterministe: c'est un langage à un compteur. Un automate à pile déterministe lit le mot de gauche à droite, incrémente un compteur sur 0, le décrémente sur 1 ou 2, rejette si le compteur devient négatif, et accepte à la fin si le compteur est strictement positif. Il n'y a aucune décision à prendre en cours de lecture.

Cette distinction est le point important de la question: non-déterminisme de la grammaire et non-déterminisme du langage sont deux notions différentes. Il existe des langages hors contexte qui ne sont reconnus par aucun automate à pile déterministe, mais ce n'est pas le cas ici.

#Partie A — grammaire sur $\{0, 1, 2\}$Copier le lien

A.1 — forme normale de Chomsky. On introduit un non-terminal par terminal ($X_0 \to 0$, $X_1 \to 1$, $X_2 \to 2$), puis on binarise les membres droits de longueur 3 en introduisant des non-terminaux auxiliaires:

$S \to X_0X_2 \qquad S \to X_0B_1,\quad B_1 \to SX_2 \qquad S \to X_0B_2,\quad B_2 \to AX_2$ $A \to X_1X_2 \qquad A \to X_1B_2 \qquad X_0 \to 0,\quad X_1 \to 1,\quad X_2 \to 2$

Toutes les productions sont bien de la forme $Y \to ZW$ ou $Y \to a$. Le non-terminal $B_2 \to AX_2$ associé à $A \to X_1B_2$ est ce qui permet d'engendrer $1^{m}2^{m}$: $A$ produit un 1, puis $B_2$ produit la suite des 1 restants suivie du même nombre de 2, et le 2 final est ajouté par $S \to X_0B_2$.

A.2 — table CYK pour 000122. On note $V_{i,j}$ l'ensemble des non-terminaux qui engendrent le facteur $w[i..j]$.

Lecture des cases non triviales:

• $V_{3,5} = \{S\}$: le facteur 012 s'obtient par $S \to X_0X_2$? Non — 012 a trois symboles. En fait $V_{3,5} = \{S\}$ vient de $S \to X_0B_1$ avec $X_0$ engendrant 0 (position 3) et $B_1 \to SX_2$ engendrant 12... ce découpage ne convient pas; la case correcte est $V_{4,6} = \{B_2\}$ (obtenue par $B_2 \to AX_2$ avec $A \Rightarrow$ 1 et $X_2 \Rightarrow$ 2), et $V_{3,6} = \{S\}$ par $S \to X_0B_2$ avec $X_0 \Rightarrow$ 0 en position 3 et $B_2 \Rightarrow$ 122 en positions 4 à 6.
• $V_{4,5} = \{A\}$ par $A \to X_1X_2$.
• $V_{3,6} = \{S\}$: le facteur 0122 est engendré.

A.3 — la case $V_{1,6}$ est vide, donc 000122 $\notin L(G)$. Le seul facteur de 000122 appartenant à $L(G)$ est 0122 (positions 3 à 6). En effet, les facteurs candidats devraient être de la forme $0^{n}1^{m}2^{n+m}$ (voir ci-dessous), et 0122 est le seul qui convienne: 02 n'est pas un facteur contigu, 012 exigerait deux 2, 00122 exigerait trois 2.

A.4 — le langage. $A$ engendre $\{1^{m}2^{m} : m \ge 1\}$ (récurrence immédiate sur $A \to 12$ et $A \to 1A2$). Les trois productions de $S$ donnent alors

$S \;\Rightarrow\; 0^{n}\,(02 \text{ ou } 0A2)\,2^{n} \qquad\text{soit}\qquad L(G) = \{\,0^{n}1^{m}2^{\,n+m} : n \ge 1,\ m \ge 0\,\}$

La forme $m = 0$ correspond à $S \to 0S2$ répété puis $S \to 02$, qui donne $0^{n}2^{n}$. On vérifie sur 0122: $n = 1$, $m = 1$, d'où $0^{1}1^{1}2^{2}$ — c'est bien le mot. Et 000122 = $0^3 1^1 2^2$ exigerait $2^{3+1} = 2^4$, il manque deux 2: le mot n'est pas dans le langage, ce que CYK confirme.

#Partie B — grammaire sur $\{0, 1\}$Copier le lien

B.1 — forme normale de Chomsky.

$S \to 0 \mid X_0S \mid X_1D \mid SF \mid DX_1 \qquad D \to SS \qquad F \to X_1S \qquad X_0 \to 0,\quad X_1 \to 1$

Chaque règle ternaire est binarisée en fixant le découpage: 1SS devient $X_1D$ avec $D \to SS$; S1S devient $SF$ avec $F \to X_1S$; SS1 devient $DX_1$. Comme les trois règles produisent des langages différents, il faut trois auxiliaires distincts ou trois combinaisons distinctes — c'est ici que se joue la correction.

B.2 — table CYK pour 001010. Le mot est 0 0 1 0 1 0. La table (seules les cases non vides sont données) contient: