MP/MP*: Option Informatique
Devoir surveillé du 12 décembre 2006
Longueur discriminante de deux automates finis

Présentation

Ce sujet comporte deux parties: un exercice de programmation et un problème.

L'exercice de programmation sera l'occasion de raisonner par induction structurelle, et de prouver le comportement d'un programme.

Le problème porte sur la détermination d'un majorant de la longueur discriminante de deux automates finis non équivalents (c'est-à-dire: qui ne reconnaissent pas le même langage). Pour ce faire, nous mettrons en œuvre des idées issues de l'algèbre linéaire. Ce sujet a été posé au concours Mines-Ponts en 2004.