Expressions rationnelles

1. Les mots qui contiennent le facteur $aa$. Oui : $baab$. Non : $abab$.
2. Les mots qui ont un nombre pair de $a$. Oui : $abab$. Non : $abbb$.
3. Les mots sans facteur $aa$. Oui : $abab$. Non : $baab$.
4. Les mots dont la longueur est un multiple de 3. Aucun mot de longueur 4 n'en fait partie ; $aaaa$ n'en fait pas partie.
5. Les mots formés d'un seul bloc de $a$ et d'un seul bloc de $b$, dans un ordre ou dans l'autre (éventuellement vides). Oui : $aabb$, $bbba$. Non : $abab$.

1. $b^*ab^*$.
2. $b^*(a + \varepsilon)b^*(a + \varepsilon)b^*$.
3. $(b + ab)^*(\varepsilon + a)$ : chaque $a$ est suivi d'un $b$, sauf peut-être le dernier.
4. $a + b + a(a + b)^*a + b(a + b)^*b$. Il ne faut pas oublier les mots d'une lettre, qui commencent et finissent par la même lettre.
5. $((a + b)(a + b)(a + b))^*$, ou $((a + b)^3)^*$ avec l'abréviation.
6. $(a + b)^*a(a + b)^*b(a + b)^* + (a + b)^*b(a + b)^*a(a + b)^*$ : un $a$ avant un $b$, ou un $b$ avant un $a$. Plus court : $a^+b(a + b)^* + b^+a(a + b)^*$, selon la première lettre.

D'autres réponses sont justes. Pour vérifier la sienne, tester les mots courts, et en particulier $\varepsilon$ et les mots d'une lettre.

1. Équivalentes. $(a^*b^*)^* \subseteq (a + b)^*$ est clair. Réciproquement, un mot de $(a + b)^*$ est une suite de lettres, et chaque lettre est dans $a^*b^*$.
2. Équivalentes : les deux dénotent $a$, $aba$, $ababa$… Un mot de $(ab)^*a$ s'écrit $abab\cdots aba$, qui se découpe aussi en $a \cdot ba \cdot ba \cdots$.
3. Non : $aab \in a^*b^*$ mais $aab \notin (ab)^*$. Et $abab \in (ab)^*$ mais $abab \notin a^*b^*$.
4. Équivalentes : $a^* + b^*$ contient $a$ et $b$, donc son étoile contient tous les mots ; l'autre inclusion est claire.
5. Équivalentes. Un mot qui ne contient pas le facteur $ab$ ne peut pas avoir un $a$ suivi (immédiatement) d'un $b$ : tous ses $b$ sont avant ses $a$, il est dans $b^*a^*$. Les deux termes couvrent donc tous les mots.

1. $\supseteq$ : un mot de $(e^*f)^*e^*$ est une suite de mots de $L(e)$ et $L(f)$, donc dans $(L(e) \cup L(f))^*$. $\subseteq$ : un mot de $(L(e) \cup L(f))^*$ est une suite $u_1 \cdots u_n$ de mots, chacun dans $L(e)$ ou dans $L(f)$. On coupe la suite après chaque $u_i$ pris dans $L(f)$ : chaque morceau est de la forme (des mots de $L(e)$) puis (un mot de $L(f)$), sauf le dernier, fait seulement de mots de $L(e)$. C'est un mot de $(e^*f)^*e^*$.
2. Les deux côtés dénotent les mots $u_0 v_1 u_1 v_2 u_2 \cdots v_n u_n$ avec $n \geq 0$, $u_i \in L(e)$, $v_i \in L(f)$ : un mot de $L(e)$, puis des couples ($f$, $e$). À gauche on groupe $u_0 \,(v_1 u_1) \cdots (v_n u_n)$, à droite $(u_0 v_1) \cdots (u_{n-1} v_n)\, u_n$.
3. $L(e) \subseteq L(e)^*$ donne $(e + f)^* \subseteq (e^* + f)^*$. Réciproquement, un mot de $L(e)^*$ est une suite de mots de $L(e)$ ; en remplaçant chaque morceau de $L(e)^*$ par cette suite, un mot de $(L(e)^* \cup L(f))^*$ devient une suite de mots de $L(e) \cup L(f)$.

1. $0[xX][0-9a-fA-F]^+$
2. $0 + -?[1-9][0-9]^*$. Le zéro est traité à part pour interdire -0 et 007.
3. $([01][0-9] + 2[0-3])\texttt{:}[0-5][0-9]$. L'heure ne peut pas s'écrire $[0-2][0-9]$, qui accepterait 29.