Minimisation et limites

1. $A \xrightarrow{a} B$, $A \xrightarrow{b} D$, $B \xrightarrow{a} E$, $B \xrightarrow{b} C$, $E \xrightarrow{b} F$ : les six états sont accessibles.
2. Rang 0 : $\{C, F\}$ et $\{A, B, D, E\}$. Rang 1 : parmi les non finals, $B$ et $E$ vont dans $\{C, F\}$ par $b$, $A$ et $D$ non : $\{A, D\}$, $\{B, E\}$, $\{C, F\}$. Rang 2 : $A$ et $D$ vont dans $\{B, E\}$ par $a$ et dans $\{A, D\}$ par $b$ ; $B$ et $E$ vont dans $\{B, E\}$ par $a$ et $\{C, F\}$ par $b$ ; $C$ et $F$ vont dans $\{B, E\}$ par $a$ et $\{A, D\}$ par $b$. Rien ne se découpe : trois classes.
3. 

Les mots qui se terminent par $ab$ : $AD$ « rien d'utile », $BE$ « on vient de lire $a$ », $CF$ « on vient de lire $ab$ ».

1. $\varepsilon^{-1}L = ab^*$ ; $a^{-1}L = b^*$ ; $b^{-1}L = \emptyset$ ; $(ab)^{-1}L = b^*$ ; $(aa)^{-1}L = \emptyset$. Trois résiduels distincts : $ab^*$, $b^*$, $\emptyset$. Automate minimal : trois états $L$ (initial), $b^*$ (final), $\emptyset$ (puits), avec $L \xrightarrow{a} b^*$, $L \xrightarrow{b} \emptyset$, $b^* \xrightarrow{b} b^*$, $b^* \xrightarrow{a} \emptyset$.
2. $a^*b^*$ (tant qu'on n'a lu que des $a$), $b^*$ (après au moins un $b$, sans $a$ ensuite), $\emptyset$ (après un $a$ qui suit un $b$). Trois états : $a^*b^*$ initial et final, $b^*$ final, puits.
3. Le mot $b^k$ est dans $(a^k)^{-1}L$ (car $a^kb^k$ a autant de $a$ que de $b$), mais pas dans $(a^{k'})^{-1}L$ pour $k' \neq k$. Les résiduels sont en nombre infini : $L$ n'est pas rationnel (théorème de Myhill et Nerode).

1. Soit $k$ ; on choisit $u = a^kb^k$. Comme $|xy| \leq k$, $y = a^j$ avec $j \geq 1$. Alors $xy^2z = a^{k+j}b^k$ a plus de $a$ que de $b$ : il n'est pas dans le langage. (Ici, il faut pomper vers le haut : retirer $y$ donnerait $a^{k-j}b^k$, qui est dans le langage.)
2. Soit $k$ ; on choisit $u = a^kba^k$, un palindrome. $y = a^j$ avec $j \geq 1$, dans le premier bloc. $xz = a^{k-j}ba^k$ n'est pas un palindrome.
3. Soit $k$ ; on choisit $u = a^{k^2}$. $y = a^j$ avec $1 \leq j \leq k$. Alors $xy^2z = a^{k^2 + j}$, et $k^2 < k^2 + j \leq k^2 + k < (k+1)^2$ : ce n'est pas un carré.
4. Si ce langage était rationnel, son intersection avec $a^*b^*$ le serait aussi (clôture par intersection). Or cette intersection est $\{a^nb^n\}$, qui n'est pas rationnel.

1. Faux : $\{a^nb^n\} \subseteq \Sigma^*$, qui est rationnel.
2. Faux : $L = \{a^nb^n\}$ et $\overline{L}$ ne sont pas rationnels (si $\overline{L}$ l'était, $L$ aussi, par complémentaire), mais $L \cup \overline{L} = \Sigma^*$ l'est.
3. Faux : avec $L = \{ab\}$, l'intersection est $\{ab\}$, finie donc rationnelle. Avec $L = \emptyset$, elle est vide.
4. Vrai : c'est un langage fini (1001 mots). La limite 1000 suffit : un automate peut compter jusqu'à 1000, pas arbitrairement loin.
5. Faux : le lemme n'est qu'une implication. Le cours donne un contre-exemple, $\{a^ib^jc^j \mid i \geq 1\} \cup \{b^jc^k\}$.