Arguments de Cardinalité pour les Automates Finis

[The TJFK]

Intuitivement la notion de reconnaissabilité pour un langage se traduit par une "cardinalité" suffisamment faible de la "mémoire" nécessaire. Du coup, est-ce qu'il existe des résultats du type: Si L et M sont deux langages vérifiant une condition (C) et que L s'injecte dans M alors si M est reconnaissable alors L aussi ?

(On se doute bien que la condition (C) doit être assez restrictive. Par exemple a^n b^n, n dans IN, n'est pas rationnel mais s'injecte dans IN qui est isomorphe à a^n, n dans IN lequel est reconnaissable.)

[sunmat]

Tous les langages sur un alphabet fini s'injectent dans IN. C'est assez trivial à montrer.

J'étais tombé sur un exercice aux oraux ENS, concernant les parties rationnelles de IN, c'est à dire les langages de la forme $ u^k u^* $. Je pense qu'on peut montrer que tout langage rationnel L se projette sur une partie rationnelle de IN pour tous les symboles de son alphabet, c'est à dire que si l'on prend tous les mots de L et qu'on supprime toutes les lettres autres qu'une certaine lettre a, on se retrouve avec une partie rationnelle de IN (quelque soit a dans l'alphabet initial de L).
Le réciproque est fausse, bien sûr, puisque $ a^nb^n $ se projette sur $ a^* $ et sur $ b^* $, qui sont rationnels, mais n'est pas rationnel lui-même.