Aspects Algébriques

Les expressions rationnelles

1.

Construire une expression rationnelle pour chacun des langages suivants :

(a)

L'ensemble des mots sur l'alphabet $\{0,1\}$ dont l'avant dernier symbole est un 0.

(b)

L'ensemble des mots sur l'alphabet $\{0,1\}$ qui commençent et qui finissent par 0.

(c)

L'ensemble des mots sur l'alphabet $\{0,1\}$ qui contiennent trois fois le symbole 1.

(d)

L'ensemble des mots sur $C=\{0,1,2,3,4,5,6,7,8,9\}$ et qui représentent les entiers en base dix, avec ou sans 0 inutiles en tête.

(e)

L'ensemble des mots sur $C\cup\{.\}$ et qui représentent en Pascal la partie décimale de nombres, avec ou sans 0 inutiles en tête (la virgule étant repréentée par un point et il y a au moins une décimale).

(f)

L'ensemble des mots sur l'alphabet $C\cup\{E,+,-,.\}$ qui représentent en Pascal l'exposant des constantes numériques. Le signe de l'exposant est facultatif, et il y a au moins un chiffre.

(g)

L'ensemble des mots sur l'alphabet $C\cup\{E,+,-,.\}$ qui représentent en Pascal les constantes numériques. La partie décimale et l'exposant étant facultatifs.

(h)

L'ensemble des mots sur l'alphabet $\{0,1\}$ qui représentent les entiers en base 2, sans 0 inutiles en tête.

(i)

L'ensemble des mots sur l'alphabet $\{0,1\}$ qui représentent les entiers pairs en base 2, sans 0 inutiles en tête.

(j)

L'ensemble des mots sur l'alphabet $\{0,1\}$ qui représentent les entiers impairs en base 2, sans 0 inutiles en tête.

(k)

$\{a^nb^m/n,m\geq 0\}$

(l)

L'ensemble des mots sur l'alphabet $\{a,b\}$ qui ne contiennent pas le motif ab.

(m)

L'ensemble des mots sur l'alphabet $\{a,b,c,\ldots,y,z\}$ dont les symboles figurent dans l'ordre alphabétique.

(n)

L'ensemble des mots sur l'alphabet $\{a,b\}$ qui contiennent une et une seule fois le motif bb.

(o)

L'ensemble des mots sur l'alphabet $\{a,b\}$ tels que :

• tout a est soit le premier symbole, soit précédé d'un b,
• tout b est soit le premier symbole, soit précédé d'un a,
• tout a est soit le dernier symbole, soit suivi d'un b,
• tout b est soit le dernier symbole, soit suivi d'un a.

2.

  Démontrer les identités suivantes :

(a)

$(a^\star)^\star=a^\star$

(b)

$(a\vert b)^\star=(a^\star b)^\star a^\star$

(c)

$(ab)^\star=\varepsilon\vert a(ba)^\star b$

(d)

$a^\star=(\varepsilon\vert a\vert\ldots\vert a^{n-1})(a^n)^\star$

3.

Déduire les identités suivantes d'après les résultats de l'exercice 2 :

(a)

$a^\star=\varepsilon\vert aa^\star=\varepsilon\vert a^\star a$

(b)

$(a\vert b)^\star=a^\star(ba^\star)^\star$

(c)

$(ab)^\star a=a(ba)^\star$

(d)

$(ab\vert a)^\star a=a(ba\vert a)^\star$

(e)

$(ab)^\star=a(ba)^\star b$

(f)

$(a\vert b)^\star b(a\vert b)^\star=(a\vert b)^\star ba^\star=a^\star b(a\vert b)^\star$