MP/MP*: Option Informatique
Devoir à rendre le jeudi 8 novembre 2007
Quelques exercices autour des langages rationnels

Présentation

Un petit texte tout simple: trois exercices sans grande prétention.

Le premier exercice est très facile; son seul (et maigre) intérêt est de montrer:

• comment prouver qu'un langage L donné est reconnu par un automate A donné;
• comment prouver qu'un langage L donné est décrit par une expression rationnelle e donnée.

Le deuxième exercice est encore plus facile, il se rédige en quelques lignes.

Le troisième exercice tourne autour du lemme de l'étoile; il faut un (petit) peu d'astuce pour établir les résultats demandés.