Aspects Algébriques

Les automates finis

1.

Construire un automate fini dont les états correspondent aux situations de famille possibles d'une personne (célibataire, marié, divorcé, veuf) et dont les flèches correspondent aux changements de situation possible. Etiqueter ces flèches par M (mariage), D (divorce) et V veuvage.

2.

Construire un automate fini qui reconnaît exactement les commentaires en langage C. On prendra comme alphabet $\{/,\star,'',a\}$ où a représentera tous les autres caractères. Tout commentaire commence par $/\star$ et fini par $\star/$. Le commentaire peut contenir des / et des $\star$, mais il ne peut pas contenir le motif $\star/$, sauf à l'intérieur d'une chaîne qui commence par " et finit par " sans contenir d'autres ". Exemple :

$$/\star\star\,\,Commentaire\,''/\star''\,toto\,''\star/'' \,\star\star/$$

3.

Construire des automates finis qui reconnaissent les langages suivants :

(a)

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

(b)

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

(c)

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

(d)

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

(e)

L'ensemble des mots sur l'alphabet $\{0,1,2,3,4,5,6,7,8, 9,E,+,-,.\}$ qui représentent en Pascal les constantes numériques.

(f)

L'ensemble des mots sur l'alphabet $\{0,1\}$ qui comportent au moins une fois le motif 10 et au moins une fois le motif 01.

(g)

$\{a^nb^m/n+m\mbox{ pair}\}$

(h)

Quel est le langage reconnu par l'automate suivant ? Lesquels de ses états sont inutiles ?