Aspects Algébriques
- 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
où a représentera tous les autres
caractères. Tout commentaire commence par
et fini
par
.
Le commentaire peut contenir des / et des
,
mais il ne peut pas contenir le motif
,
sauf
à l'intérieur d'une chaîne qui commence par " et
finit par " sans contenir d'autres ". Exemple :
- 3.
- Construire des automates finis qui reconnaissent les langages
suivants :
- (a)
- L'ensemble des mots sur
dont l'avant dernier
symbole est 0.
- (b)
- L'ensemble des mots sur l'alphabet
qui
commencent et qui finissent par 0.
- (c)
-
- (d)
-
- (e)
- L'ensemble des mots sur l'alphabet
qui représentent en Pascal les
constantes numériques.
- (f)
- L'ensemble des mots sur l'alphabet
qui
comportent au moins une fois le motif 10 et au moins
une fois le motif 01.
- (g)
-
- (h)
- Quel est le langage reconnu par l'automate suivant ? Lesquels
de ses états sont inutiles ?
Jean-Baptiste Yunes
2000-02-18