Aspects Algébriques

Les codes

1.

Calculer X^-1.Y et Y.X^-1 pour :

(a)

$X=\{a,b\}$, $Y=\{a^2,ba,ab^5,bab\}$

(b)

$X=\{aba,b^2c\}$, $Y=\{ba,bbac,bbca,b^4,ab,aba^3\}$

(c)

$X=\{a\}$, $Y=a^\star b$

(d)

$X=\{a,b\}$, Y=a⁺b

2.

  Les ensembles suivants sont-t'ils des codes ? préfixes ? suffixes ? bipréfixes ?

(a)

$X=\{a,b\}$

(b)

$X=\{a,ba,bb\}$

(c)

$X=\{a,b,ab\}$

(d)

$X=\{a,ab,ba\}$

(e)

$X=a^\star b$

(f)

$X=\{ab,bc,ac,abc\}$

(g)

$X=\{ab,a^3b,bcb,ab^2,c,bac,ac\}$

(h)

$X=\{a^2,a^3,a^3b,ba\}$

(i)

$X=\{aa,aba,a^3b^4,abb,ba,bb,aba^4b^2\}$

(j)

$X=\{aaa,bbb,aab,aaab,abb,abaa,bba\}$ et X.a

3.

Calculer les ensembles générateurs minimaux correspondants aux monoïdes engendrés par les ensembles de l'exercice 2 et qui ne forment pas un code.

4.

Démontrer que :

$$M\mbox{ sous-mono\uml {\i}de libre de }X^\star \Longrightarrow G_M\mbox{ est un code}$$

5.

Démontrer que :

$$C\subset X^\star \Longrightarrow C^\star\mbox{ est libre et } C=G_{C^\star}$$

6.

Démontrer le théorème suivant : Soit $A\subset X^\star$,

$$A^\star\mbox{ libre}\Longleftrightarrow \forall f\in X^\star... ...ar\not=\phi$ \\ \end{tabular}\right\}\Rightarrow f\in A^\star$$

7.

Montrer que pour un monoïde M, tout générateur de M contient son générateur minimal.