Propriétés de clôture

1. $((ab^*c + d)^*a)^t = a^t\,((ab^*c + d)^*)^t = a\,((ab^*c + d)^t)^* = a\,((ab^*c)^t + d)^* = a\,(c\,(b^*)^t\,a + d)^* = a(cb^*a + d)^*$.
2. Transitions inversées : $0 \xrightarrow{b} 0$, $1 \xrightarrow{a} 0$, $0 \xrightarrow{b} 1$, $2 \xrightarrow{a} 1$, $2 \xrightarrow{a, b} 2$ ; 2 devient initial, 0 final. Il n'est pas déterministe : depuis 2, la lettre $a$ mène en 2 et en 1 ; depuis 0, $b$ mène en 0 et en 1. Il reconnaît le transposé du langage, c'est-à-dire… les mots qui contiennent $aa$ : un mot contient $aa$ si et seulement si son miroir le contient.

1. Le DFA est complet : on échange simplement finals et non finals. 0 et 1 deviennent finals, 2 ne l'est plus (c'est désormais un puits).

2. On supprime le puits 2 (inutile), on normalise ($I \to 0$, $0 \to F$, $1 \to F$). Supprimer 1 : prédécesseur 0 (par $a$), successeurs 0 (par $b$) et $F$. $(0, 0)$ : $b + ab$ ; $(0, F)$ : $\varepsilon + a$. Supprimer 0 : $(b + ab)^*(\varepsilon + a)$. C'est l'expression de la feuille 2.
3. Après l'échange, 0 et 1 sont finals. Comme 0 est initial et boucle sur les deux lettres, tous les mots sont acceptés, $aa$ compris. L'échange ne donne le complémentaire que sur un automate déterministe et complet ; ici l'automate n'est ni l'un ni l'autre.

1.

Cinq couples accessibles, sur six possibles : $(1, 1)$ ne l'est pas (on n'est en 1 dans $L_1$ qu'après un $a$, et en 1 dans $L_2$ qu'après un $b$).

2. Intersection : $(2, 1)$. Union (les deux DFA sont complets) : les couples où une composante est finale, $(2, 0)$, $(2, 1)$, $(0, 1)$. Différence : $L_1$ final et $L_2$ non final, $(2, 0)$.
3. Un plus court chemin de $(0, 0)$ à $(2, 1)$ : $a, a, b$. Le mot $aab$.

1. $(ab)^* \subseteq P$ (mots de longueur paire) si et seulement si $(ab)^* \cap \overline{P} = \emptyset$, où $\overline{P}$ est l'ensemble des mots de longueur impaire.
2. DFA de $(ab)^*$ : $0 \xrightarrow{a} 1 \xrightarrow{b} 0$, 0 initial et final. DFA de $\overline{P}$ : $E \xrightarrow{a,b} O \xrightarrow{a,b} E$, $E$ initial, $O$ final. Produit depuis $(0, E)$ : $(0, E) \xrightarrow{a} (1, O) \xrightarrow{b} (0, E)$. Le seul couple final possible, $(0, O)$, n'est pas accessible : l'intersection est vide, l'inclusion est vraie.

1. Même automate, avec pour état initial $\delta(q_0, a)$.
2. C'est $L \cap ((a + b)(a + b))^*$ : intersection de deux rationnels. Ou directement : produit de $A$ avec l'automate à deux états de la parité de la longueur.
3. On fait tourner deux copies de $A$ en même temps sur $u$ : la première part de $q_0$ ; la seconde part d'un état $p$ deviné au départ, qui doit être celui où la première arrivera. États : triplets $(p, q, r)$, où $p$ est l'état deviné (il ne change jamais), $q$ l'état de la première copie, $r$ celui de la seconde. Initiaux : les $(p, q_0, p)$ pour tout $p \in Q$. Transitions : $(p, q, r) \xrightarrow{a} (p, \delta(q, a), \delta(r, a))$. Finals : les $(p, p, r)$ avec $r \in F$. À la fin de $u$, la première copie est en $p$ (le milieu de $uu$ était bien $p$) et la seconde a lu le second $u$ depuis $p$ et finit dans $F$. C'est un NFA (plusieurs initiaux) à $|Q|^3$ états.