De la complexité des mots - Lycée Gay Lussac (Chauny)

Établissement
Lycée Gay Lussac (Chauny)
Année
2018-2019
Résumé
Considérons par exemple le mot infini 011011011011011011.... (on répète indéfiniment la suite constituée d’un 0 et de deux 1) Le nombre de mots d’une seule lettre apparaissant dans ce mot est égal à 2 (pourquoi ?) Le nombre de mots de deux lettres apparaissant dans ce mot est égal à 3 (pourquoi ?) Le nombre de mots de trois lettres apparaissant dans ce mot est égal à 3 (pourquoi ?) Plus généralement, on peut définir une suite d’entiers dont le n-ième terme est égal au nombre de mots de n lettres apparaissant dans le mot initial. Ici, les premiers termes de la suite sont : 2, 3, 3.
• Que peut-on dire du comportement de cette suite :
- lorsque l’on part de l’exemple présenté ?
- lorsque l’on part d’un mot périodique infini ?
- lorsque l’on part d’un mot infini quelconque ?
Type de présentation au congrès
Exposé