Aspects Algébriques

Relations engendrées par un langage

Relations engendrées par un automate

Rappel : Soit ${\cal L}$ un langage. On définit la relation suivante :

$${\cal R}_{\cal L}:\,\forall\,x,y\in\Sigma^\star,\, x{\cal R}... ...\in{\cal L})\bigvee(xz\not\in{\cal L}\wedge yz\not\in{\cal L})$$

Rappel : Soit ${\cal M}$ un automate. On définit la relation suivante :

$${\cal R}_{\cal M}:\,\forall\,x,y\in\Sigma^\star,\, x{\cal R}_{\cal M}y\Longleftrightarrow \delta(q_0,x)=\delta(q_0,y)$$

1.

 Soit ${\cal L}=0^\star 10^\star$. Combien ce langage définit-il de classes d'équivalences ? Donner une expression rationnelle pour chacune d'elle.

2.

Montrer que si $x{\cal R}_{\cal M}y$ alors $\forall\,z\in \Sigma^\star,\,xz{\cal R}_{\cal M}yz$.

3.

  Donner les classes d'équivalences pour chacun des états de l'automate ${\cal M}$ suivant :

4.

Montrer que la relation ${\cal R}_{\cal M}$ est plus fine que la relation ${\vert cal R}_{\cal L}$.

5.

Montrer que ${\cal M}$ (du 3) reconnaît ${\cal L}$ (du 1).

6.

En déduire un automate ``minimal'' reconnaissant ${\cal L}$.