Aspects Algébriques

Le monoïde libre

Rappels : Soit $\Sigma$ un alphabet fini. Pour $X,Y\subseteq \Sigma^\star$, on définit :

$X.Y=\{x.y/x\in X\mbox{ et }y\in Y\}$

$X^\star=\sum_{i\geq 0}X^i$

$X^+=\sum_{i>0}X^i$

où $X^0=\{\varepsilon\}$ et pour i>0,Xⁱ=X^i-1.X

1.

Soit $\Sigma=\{a,b\}$. Calculer X.Y et Y.X pour :

(a)

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

(b)

$X=\{\varepsilon\}$, $Y=\{ba,bb\}$

(c)

$X=\phi$, $Y=\{ba,bb\}$

(d)

$X=\{\mbox{les mots ayant un nombre pair de }a\}$, $Y=ab^\star$. Donner une expression rationnelle pour X.

(e)

$X=\{ab,ab^3,ab^5,\ldots,ab^{2n+1},\ldots\}$ et $Y=\{a,b^2a,\ldots,b^{2n}a,\ldots\}$. Donner une expression rationnelle pour X et Y.

2.

Calculer $X^\star$ et X⁺ pour :

(a)

$X=\{aa,ab,ba,bb\}$

(b)

$X=\phi$

(c)

$X=\{\varepsilon\}$

(d)

$X=\{w\in\{a,b\}^\star,\vert w\vert _a\not=\vert w\vert _b\}$

A-t'on toujours $X^\star=X^++\{\varepsilon\}$, $X^+=X.X^\star$, $X^+=X^\star-\{\varepsilon\}$ ? Sous quelles conditions ?

3.

Montrer les égalités suivantes :

(a)

$(X^\star)^\star=X^\star$

(b)

$(X.Y)^\star.X=X.(Y.X)^\star$

(c)

$(X.Y)^\star=\{\varepsilon\}+X.(Y.X)^\star.Y$