Automates finis

1. $\varepsilon$ : oui (0 est initial et final). $abba$ : on finit en 2, non. $bbb$ : on revient en 0, oui. $babab$ : trois $b$ (en positions 1, 3 et 5), on revient en 0, oui.
2. L'état $i$ retient le nombre de $b$ lus, modulo 3 ; les $a$ ne changent rien. Le langage : les mots dont le nombre de $b$ est un multiple de 3.
3. Déterministe : oui. Complet : oui, chaque état a une transition par lettre. Émondé : oui, chaque état est accessible et co-accessible.

1. Quatre états : 0 « aucun début de $aba$ en cours », 1 « on vient de lire $a$ », 2 « on vient de lire $ab$ », 3 « $aba$ a été lu » (final, boucle sur $a$ et $b$).

Le piège est la transition $1 \xrightarrow{a} 1$ : après $aa$, le second $a$ peut commencer un $aba$. Et $2 \xrightarrow{b} 0$ : après $abb$, plus rien n'est en cours.

2. Quatre états, un par couple de parités ($a$ pair ou impair, $b$ pair ou impair). Initial : (pair, pair). Final : (pair, impair). Lire $a$ change la première parité, lire $b$ la seconde. C'est le produit de deux automates à deux états (chapitre 6).

3. Si $u$ vaut $n$, $u0$ vaut $2n$ et $u1$ vaut $2n + 1$. Il suffit de retenir $n$ modulo 3 : trois états 0, 1, 2, initial et final 0, et $r \xrightarrow{d} (2r + d) \bmod 3$.

Par exemple $110$ (six) : $0 \xrightarrow{1} 1 \xrightarrow{1} 0 \xrightarrow{0} 0$, accepté.

1. Accessibles : 0, 1, 2, 3 (4 n'a pas de transition entrante depuis 0). Co-accessibles : 0, 1, 2, 4 (depuis 3, on ne sort pas de 3). Utiles : 0, 1, 2.
2. $0 \xrightarrow{a} 1 \xrightarrow{b} 2 \xrightarrow{a} 1$, 2 final. Il reconnaît $(ab)^+$ : $ab$, $abab$, …
3. Non : il manque $0 \xrightarrow{b}$, $1 \xrightarrow{a}$, $2 \xrightarrow{b}$. On ajoute un puits $p$, non final, avec $0 \xrightarrow{b} p$, $1 \xrightarrow{a} p$, $2 \xrightarrow{b} p$ et $p \xrightarrow{a, b} p$. L'état 3 de l'automate d'origine jouait déjà ce rôle pour $0 \xrightarrow{b}$.

1. Les mots qui contiennent le facteur $aba$ (le même qu'au deuxième exercice).
2. $abba$ : $\{0\} \xrightarrow{a} \{0, 1\} \xrightarrow{b} \{0, 2\} \xrightarrow{b} \{0\} \xrightarrow{a} \{0, 1\}$. Pas d'état final : refusé.

$babab$ : $\{0\} \xrightarrow{b} \{0\} \xrightarrow{a} \{0, 1\} \xrightarrow{b} \{0, 2\} \xrightarrow{a} \{0, 1, 3\} \xrightarrow{b} \{0, 2, 3\}$. Contient 3 : accepté.

3. Un chemin reste en 0 jusqu'au bout. D'autres « devinent » un début de $aba$ au deuxième ou au quatrième caractère. Deviner au deuxième : $0 \xrightarrow{b} 0 \xrightarrow{a} 1 \xrightarrow{b} 2 \xrightarrow{a} 3 \xrightarrow{b} 3$, réussi. Deviner au quatrième : $\ldots \xrightarrow{a} 1 \xrightarrow{b} 2$, puis le mot est fini, échec. Il y a aussi des chemins qui ne sont pas lus jusqu'au bout (blocage). Au total, trois chemins lisent tout le mot, dont un seul réussi : il suffit d'un.

1. Si l'état n'est pas initial, ou pas final, aucun chemin n'est réussi : $\emptyset$. S'il est initial et final, les chemins sont les boucles ; si $S \subseteq \Sigma$ est l'ensemble des lettres qui étiquettent une boucle, le langage est $S^*$. Donc : $\emptyset$, ou $S^*$ pour une partie $S$ de $\Sigma$ (avec $S = \emptyset$, on obtient $\{\varepsilon\}$).
2. États $p$ (initial) et $q$. La lettre $a$ mène de $p$ à $p$ ou à $q$, et de $q$ à $p$ ou à $q$. Selon les cas et selon les états finals, on obtient notamment $\emptyset$, $a^*$, $\{\varepsilon\}$, $a^+$, $(aa)^*$, $a(aa)^*$. Par exemple $p \xrightarrow{a} q \xrightarrow{a} p$ avec $p$ final donne les mots de longueur paire.