Aspects Algébriques

Langages résiduels

1.

Démontrer les propositions suivantes pour tout $a\in A$ et $r,s\in\mbox{Rat}(A^\star)$ :

• a^-1(r|s)=a^-1r|a^-1s
• Si $\varepsilon\not\in r, a^{-1}(rs)=(a^{-1}r)s$
• Si $\varepsilon\in r, a^{-1}(rs)=(a^{-1}r)s\vert a^{-1}s$
• $a^{-1}(r^\star)=(a^{-1}r)r^\star$

2.

Montrer que $\forall u,v\in A^\star,\,\forall L\subset A^\star\, (uv)^{-1}L=v^{-1}(u^{-1}L)$

3.

On veut étudier l'expression rationnelle $r=(a\vert b)^\star b (a\vert ab)^\star$. Donner des expressions rationnelles pour les langages :

• a^-1r,
• b^-1r,
• (aa)^-1r,
• (ab)^-1r,
• (ba)^-1r,
• (bb)^-1r.

En déduire la liste de tous les langages distincts de la forme u^-1r pour tout $u\in A^\star$ et pour $r=(a\vert b)^\star b (a\vert ab)^\star$.

En déduire l'automate déterministe minimal qui reconnaît r, et donner une expression rationnelle équivalente à r.