Mot infini
En mathématiques, notamment en combinatoire, en informatique théorique, en théorie des automates et en combinatoire des mots, un mot infini sur un alphabet , est une suite infinie d'éléments pris dans un ensemble , en général fini. Un mot infini est plutôt noté, comme pour les mots finis, sous la forme
Les mots infinis ont de nombreux usages. Ce sont :
- les suites caractéristiques, à éléments ou , d'ensembles d'entiers naturels ;
- les représentations de partitions de l'ensemble des entiers naturels ;
- les représentations des développements de nombres réels dans une base donnée ;
- les trajectoires dans un système dynamique symbolique ;
- les mots infinis reconnus par des automates ;
- les évolutions de programmes dans la vérification de modèles.
Les exemples de mots infinis les plus connus sont le mot de Fibonacci, et plus généralement les mots sturmiens, et la suite de Prouhet-Thue-Morse et plus généralement les suites automatiques.
Définition et notations
Un mot infini sur un alphabet est une suite infinie
composée d'éléments de .
On peut donc voir un mot infini comme une suite indexée par les entiers naturels — parfois la numérotation commence à 1 — ou comme une fonction des entiers naturels dans l'alphabet . On peut aussi voir le mot comme un produit infini de lettres, et on rencontre alors la notation
- .
Cette notation a l'avantage de s'étendre au produit infini de mots au lieu du produit infini de lettres.
On note ou l'ensemble des mots infinis sur . On peut considérer aussi des mots infinis bilatères, indexés par au lieu de .
L'opérateur de répétition infinie est employé pour dénoter ou construire des mots infinis. Ainsi,
- est le mot infini composé uniquement de lettres ;
- , où est un ensemble de mots finis, est l'ensemble des mots infinis de la forme , où chaque est dans .
Le produit de concaténation de deux mots infinis n'existe pas, mais le produit d'un mot fini et d'un mot infini , noté , est le mot formé en ajoutant le mot après le mot . Ainsi :
- est le mot infini composé de la lettre suivie uniquement de lettres ;
- est l'ensemble des mots infinis commençant par un nombre fini de lettres suivies de lettres ;
- est l’ensemble des mots infinis contenant un nombre fini d'occurrences de la lettre .
Comme exemple de l'usage des notations, on considère la suite caractéristique des carrés. C'est un mot infini , avec si et seulement si est un carré, et sinon. Cette définition fonctionnelle fournit le produit
- .
L'ensemble des mots finis ou infinis est noté .
Topologie
L'ensemble est doté d'une distance définie comme suit :
Pour deux mots et de , on note la longueur du plus long préfixe commun de et . C'est un entier naturel ou . La distance est le nombre
- .
Il est clair que si et seulement si , et aussi que . L'inégalité triangulaire traditionnelle d'une distance est renforcé par l'inégalité
pour tout mot infini , qui en fait une distance ultramétrique. Cette inégalité revient en effet à
et pour se convaincre que cette formule est valide, supposons que . Alors les mots et coïncident sur le préfixe commun entre et mais pas au-delà, donc .
La notion de convergence est usuelle : une suite de mots infinis converge vers un mot infini si quand . Par exemple, la suite de mots infinis tend vers .
La topologie ainsi définie sur l'ensemble est la topologie produit de la topologie discrète sur l'alphabet . L'espace est un espace de Cantor, c'est-à-dire un espace compact totalement disconnecté, sans point isolé.
On étend comme suit la topologie aux mot finis et infinis. On ajoute à l'alphabet une lettre supplémentaire , et on identifie à . Ainsi, une suite de mots finis converge vers un mot infini si la longueur du plus long préfixe commun entre et tend vers l'infini avec . On écrit alors
- .
Par exemple, la suite de mot finis tend vers .
Un cas particulier de cette situation se présente lorsque les mots sont chacun préfixe du mot suivant. Pourvu que la suite des longueurs tende vers l'infini, la limite est alors le mot infini dont les sont des préfixes.
Mots morphiques
Un morphisme est prolongeable pour une lettre de si est un préfixe propre de , et si de plus, la suite des longueurs de itérés tend vers l'infini lorsque tend vers l'infini.
Si est prolongeable en , il existe un mot non vide tel que . En itérant, on obtient l'expression :
La suite de ces mots converge vers un mot infini noté :
Ce mot est le mot infini engendré par en . Un mot infini sur un alphabet est purement morphique s'il existe un morphisme et une lettre dans tel que
Un mot infini sur un alphabet est morphique s'il est l'image, par un morphisme littéral (lettre à lettre), d'un mot purement morphique.
Exemples
— Le morphisme de Thue-Morse est défini par
- .
Il est prolongeable à la fois en la lettre et en la lettre . Pour la lettre , on obtient le mot infini de Thue-Morse :
et pour la lettre , on obtient le mot opposé
— Le morphisme de Fibonacci est défini par
- .
Il est prolongeable en ; en itérant, on obtient le mot infini :
- .
Ces deux mots infinis sont donc purement morphiques.
— Le morphisme :
est prolongeable en . En itérant, on obtient le mot infini :
qui, à la première lettre près, est la suite caractéristique des carrés (0, 1, 4, 9, 16, etc). En lui appliquant le morphisme littéral qui identifie et , on obtient exactement la suite caractéristique, qui est donc un mot morphique.
— Lorsque le morphisme qui est itéré est uniforme, c'est-à-dire lorsque les images des lettres ont toutes la même longueur (par exemple, le morphisme de Thue-Morse est uniforme), la suite engendrée est une suite automatique.
Décalage
L'opérateur de décalage est défini, pour tout mot infini
- ,
par
- .
La même définition vaut pour les mots infinis bilatères. Dans ce cas, est une bijection. L'opérateur de décalage est une fonction continue.
Un système dynamique symbolique sur l'alphabet est un ensemble non vide de mots infinis sur qui est :
- fermé pour l’opérateur de décalage ;
- fermé pour la topologie.
La même définition vaut pour les mots infinis bilatères.
Ensemble rationnel de mots infinis
Un ensemble rationnel (on dit aussi langage rationnel ou ω-langage rationnel) de mots infinis sur un alphabet est une union finie d'ensembles de la forme
où et sont des langages rationnels sur . La famille des ensembles rationnels de mots infinis est fermée par union, et par produit à gauche par un langage rationnel sur .
Exemples :
- Le langage des mots sur et qui ont un nombre fini de est rationnel.
- Le langage des mots sur et qui contiennent une infinité de est rationnel.
Bibliographie
- (en) Dominique Perrin et Jean Éric Pin, Infinite Words : Automata, Semigroups, Logic and Games, Amsterdam/Boston, Academic Press, , 538 p. (ISBN 978-0-12-532111-2, lire en ligne)
- (en) Samuel Eilenberg, Automata, Languages and Machines, Vol. A, New York, Academic Press, coll. « Pure and Applied Mathematics » (no 58), , xvi+451 (ISBN 978-0-12-234001-7)
- (en) Erich Grädel, Wolfgang Thomas et Thomas Wilke (éditeurs), Automata, Logics, and Infinite Games : A Guide to Current Research, Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 2 500), , viii+385 (ISBN 978-3-540-00388-5, lire en ligne).
Portail des mathématiques
Portail de l'informatique théorique