Aspects Algébriques

Fermeture de $\mbox{Rec}(X^\star)$ et de $\mbox{Rat}(X^\star)$

1.

Montrer que si ${\cal L}$ est un langage rationnel, alors $\overline{\cal L}=\{w/\overline{w}\in{\cal L}\}$ est rationnel.

2.

Montrer que le langage ${\cal L}_3=\{a^nb^n/n\geq 0\}$ n'est pas rationnel. En déduire que les langages ${\cal L}_4=\{a^nb (bc)^n/n\geq 0\}$; ${\cal L}_5=\{a^nb^m/m\geq n\}$; ${\cal L}_6=\{w/\vert w\vert _a=\vert w\vert _b\}$ ne sont pas rationnels.

3.

Soit $\Sigma$ un alphabet contenant une seule lettre a. On appellera suite arithmétique sur $\Sigma$ tout langage de la forme :

$$\{a^{r+kn}/n\geq 0\}$$

Montrer que ${\cal L}\subseteq \Sigma^\star$ est rationnel si et seulement si ${\cal L}$ est une réunion finie de langages d'ensembles finis ou de suites arithmétiques.

4.

Soit $\Sigma=\{a,b\}$, $\Delta=\{0,1\}$, $h:\Sigma\rightarrow \Delta$ tel que h(a)=00, h(b)=010, et ${\cal L}= 01^\star 0(001^\star 0)^\star$. Montrer que $h^{-1}({\cal L})$ est reconnaissable; déduisez une expression rationnelle pour $h^{-1}({\cal L})$.