Corrigé des exercices

Chapitre 4option informatique
Corrigé des exercices
Automates finis déterministes

Pour lire les entiers à partir du bit de poids le plus faible, il suffit de considérer l"automate transposé, c"est-à-dire
celui obtenu en inversant l"ordre des transitions et en échangeant états initiaux et états finaux. En général, la
transposée d"un automate déterministe est non déterministe, mais l"automate ci-dessus fait exception.q

Exercice 3
Il y a trois types de mots dans ce langage : ceux qui contiennent au moins unaet unbavant le
dernier caractère (étatq6), ceux qui ne contiennent que desaet qui sont de longueur au moins 2 (étatq3), ceux
qui ne contiennent que desbet qui sont de longueur au moins 2 (étatq5).q

Exercice 4
1.
Les mots deL0sont les mots qui commencent par 1 et qui comportent au moins un 0 dans leur écriture.
D"où l"automate :

Exercice 5
On définit deux suites (Ri) et (Si) de parties de Q en posant R0=fq0g, S0= F et pour touti2N:
il existe une transition d"un élément de Riàqo
il existe une transition deqà un élément de Sio
Ces deux suites sont croissantes dansQfini donc sont stationnaires. Leurs limitesRetSsont atteintes dès lors
que deux termes consécutifs sont égaux et dans ce casRest l"ensemble des états accessibles etSl"ensemble
des états co-accessibles. Il suffit dès lors de supprimer les états qui n"appartiennent pas àR\Sainsi que les
transitions dans lesquelles ces états interviennent pour obtenir l"automate émondé demandé.
Commençons par une fonction qui détermine les états accessibles en suivant l"algorithme exposé ci-dessus :letaccessible a =let rec aux1 b =function