MP/MP*: Option Informatique
Devoir à rendre le jeudi 9 novembre 2006
Mots directeurs d'un automate fini

Présentation

Un mot m est directeur pour un automate fini déterministe complet A si l'état delta(q,m) dans lequel on se trouve après lecture du mot m ne dépend pas de l'état q dans lequel on commence cette lecture.

Nous étudierons quelques propriétés du langage constitué par les mots directeurs d'un a.f.d.c. En particulier, nous montrerons que ce langage est rationnel

Nous étendrons ensuite la notion de mot directeur aux automates non-déterministes: ceci peut se faire de trois façons différentes, et nous permettra de mettre en évidence d'autres familles de langages rationnels.

Les questions plus délicates sont signalées par une ou deux étoiles.