Des expressions aux automates

1. Trois symboles de base ($a$, $b$, $b$), un $+$, une étoile : $2 \times 5 = 10$ états.
2. 
3. Un seul. Le second $b$ doit être celui de $8 \to 9$, donc le premier est lu dans l'étoile : $0 \to 1 \to 4 \xrightarrow{b} 5 \to 6 \to 7 \to 8 \xrightarrow{b} 9$, avec six transitions spontanées. L'automate de Thompson a beaucoup de chemins partiels (on peut entrer dans la branche $a$, repasser par 1…), mais cela ne donne pas plusieurs chemins réussis pour un même mot.

1. $a^+b^*$ : un ou plusieurs $a$ (la transition $1 \to 0$ permet de recommencer), puis des $b$.
2. $\mathrm{clo}^{-1}(0) = \{0, 1\}$, $\mathrm{clo}^{-1}(1) = \{1\}$, $\mathrm{clo}^{-1}(2) = \{1, 2\}$.
3. $0 \xrightarrow{a} 1$ : 0 et 1 sont dans la clôture arrière de 0, on ajoute $1 \xrightarrow{a} 1$. $2 \xrightarrow{b} 2$ : on ajoute $1 \xrightarrow{b} 2$. L'état 1 mène spontanément à l'état final 2 : il devient final.

Vérification : $\varepsilon$ refusé (0 n'est pas final), $a$ accepté (en 1), $ab$ accepté (en 2), $b$ refusé (bloqué en 0). Comme dans l'automate d'origine.

1. Les mots qui se terminent par $aa$ ou par $bb$.

2.

3. Cinq états, sur les $2^4 = 16$ parties : onze ne sont pas accessibles. Chaque état retient la dernière lettre lue, et si elle répète la précédente.

1. $\{0, 1, 2\}$ pour 0, $\{1, 2\}$ pour 1, $\{2\}$ pour 2.
2. Départ : $\{0, 1, 2\}$. Par $a$ : $\{0\}$, de clôture $\{0, 1, 2\}$. Par $b$ : $\{1\}$, de clôture $\{1, 2\}$. Par $c$ : $\{2\}$. Depuis $\{1, 2\}$ : $b$ mène à $\{1, 2\}$, $c$ à $\{2\}$, $a$ nulle part. Depuis $\{2\}$ : $c$ mène à $\{2\}$. Les trois parties contiennent 2 : elles sont toutes finales.

1. $0 \xrightarrow{a, b} 0$, $0 \xrightarrow{a} 1$, $1 \xrightarrow{a, b} 2$, $2 \xrightarrow{a, b} 3$, 3 final.
2. $u$ et $v$ diffèrent à au moins une position $i \in \{1, 2, 3\}$ ; disons $u_i = a$ et $v_i = b$. Prenons $w = a^{i-1}$, de longueur $i - 1$. Dans $uw$, la troisième lettre avant la fin est $u_i = a$ : $uw \in L_3$. Dans $vw$, c'est $v_i = b$ : $vw \notin L_3$.
3. Dans un DFA, si $u$ et $v$ menaient au même état, $uw$ et $vw$ aussi, et ils seraient tous deux acceptés ou tous deux refusés. Les 8 mots de longueur 3 mènent donc à 8 états différents.
4. Même raisonnement : $L_k$ a un NFA à $k + 1$ états, et tout DFA en a au moins $2^k$. La déterminisation peut coûter une exponentielle, et ce n'est pas la faute de l'algorithme.