Discussion :

[Virgile le chat]

Bonjour,
je m'amuse à faire le sujet d'info pour le concours d'entrée à l'ENS (voir pièce jointe).
C'est un sujet très intéressant sur les mots de langages formels et leurs sous-mots. Les questions 11 à 14 proposent une méthode pour détecter si oui ou non, un mot est un sous-mot accepté par une expression rationnelle.
On utilise les résidus d'un langage L sur un mot u (voir explications avent la q. 11). La question 11 suggère d'utiliser la récursivité pour construire l'expression rationnelle <a>L(e) à partir de l'expression rationnelle L(e) (c'est la q. 14). Or les formules de la question 11 ne sont, en fait, pas des égalités mais des inclusions, ce qui interdit de construire (sous forme d'un arbre binaire) récursivement <a>L(e) à partir de L(e) (L(e) étant elle-même représentée par un arbre binaire). En effet il est nécessaire d'avoir les égalités dans les formules de la question 11.
Si vous connaissez ce problème, si vous essayez de le faire, je serais ravi de discuter avec quelqu'un qui est intéressé.
Si quelqu'un sait où trouver un corrigé, dites-le moi, j'aimerais bien avoir la solution à mon problème...
Merci !

Virgile le chat.