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 $A$, est une suite infinie $x=(a_{0},a_{1},\ldots ,a_{n},\ldots )$ d'éléments pris dans un ensemble $A$, en général fini. Un mot infini est plutôt noté, comme pour les mots finis, sous la forme

$x=a_{0}a_{1}\cdots a_{n}\cdots$

Les mots infinis ont de nombreux usages. Ce sont :

• les suites caractéristiques, à éléments $0$ ou $1$, 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 $A$ est une suite infinie

$x=a_{0}a_{1}\cdots a_{n}\cdots$

composée d'éléments de $A$.

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 $A$. On peut aussi voir le mot comme un produit infini de lettres, et on rencontre alors la notation

$x=\prod _{n=0}^{\infty }a_{n}$.

Cette notation a l'avantage de s'étendre au produit infini de mots au lieu du produit infini de lettres.

On note $A^{\mathbb {N} }$ ou $A^{\omega }$ l'ensemble des mots infinis sur $A$. On peut considérer aussi des mots infinis bilatères, indexés par $\mathbb {Z}$ au lieu de $\mathbb {N}$.

L'opérateur $\omega$ de répétition infinie est employé pour dénoter ou construire des mots infinis. Ainsi,

• $a^{\omega }$ est le mot infini composé uniquement de lettres $a$;
• $X^{\omega }$, où $X$ est un ensemble de mots finis, est l'ensemble des mots infinis de la forme $x_{0}x_{1}\cdots x_{n}\cdots$, où chaque $x_{i}$ est dans $X$.

Le produit de concaténation de deux mots infinis n'existe pas, mais le produit d'un mot fini $u$ et d'un mot infini $x$, noté $ux$, est le mot formé en ajoutant le mot $x$ après le mot $u$. Ainsi :

• $ba^{\omega }$ est le mot infini composé de la lettre $b$ suivie uniquement de lettres $a$;
• $b^{\star }a^{\omega }$ est l'ensemble des mots infinis commençant par un nombre fini de lettres $b$ suivies de lettres $a$;
• $\{a,b\}^{\star }a^{\omega }$ est l’ensemble des mots infinis contenant un nombre fini d'occurrences de la lettre $b$.

Comme exemple de l'usage des notations, on considère la suite caractéristique des carrés. C'est un mot infini $w=c_{0}c_{1}\cdots c_{n}\cdots$, avec $c_{n}=1$ si et seulement si $n$ est un carré, et $c_{n}=0$ sinon. Cette définition fonctionnelle fournit le produit

$c=11001000010000001\cdots =\prod _{n=0}^{\infty }1(00)^{n}$.

L'ensemble des mots finis ou infinis est noté $A^{\infty }=A^{\star }\cup A^{\omega }$.

Topologie

L'ensemble $A^{\omega }$ est doté d'une distance définie comme suit :

Pour deux mots $x$ et $y$ de $A^{\omega }$, on note $\ell (x,y)$ la longueur du plus long préfixe commun de $x$ et $y$. C'est un entier naturel ou $+\infty$. La distance $d(x,y)$ est le nombre

$d(x,y)=2^{-\ell (x,y)}$.

Il est clair que $d(x,y)=0$ si et seulement si $x=y$, et aussi que $d(x,y)=d(y,x)$. L'inégalité triangulaire traditionnelle d'une distance est renforcé par l'inégalité

$d(x,y)\leq \max(d(x,z),d(z,y))$

pour tout mot infini $z$, qui en fait une distance ultramétrique. Cette inégalité revient en effet à

$\ell (x,y)\geq \min(\ell (x,z),\ell (z,y))$

et pour se convaincre que cette formule est valide, supposons que $\ell (x,z)>\ell (x,y)$. Alors les mots $x$ et $z$ coïncident sur le préfixe commun entre $x$ et $y$ mais pas au-delà, donc $\ell (x,y)=\ell (z,y)$.

La notion de convergence est usuelle : une suite $(x_{n})$ de mots infinis converge vers un mot infini $x$ si $d(x_{n},x)\to 0$ quand $n\to \infty$. Par exemple, la suite de mots infinis $x_{n}=a^{n}b^{n}a^{\omega }$ tend vers $a^{\omega }$.

La topologie ainsi définie sur l'ensemble $A^{\omega }$ est la topologie produit de la topologie discrète sur l'alphabet $A$. 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 $A$ une lettre supplémentaire $\$$, et on identifie $A^{\star }$ à $A^{\star }\$^{\omega }$. Ainsi, une suite $(x_{n})$ de mots finis converge vers un mot infini $x$ si la longueur du plus long préfixe commun entre $x_{n}$ et $x$ tend vers l'infini avec $n$. On écrit alors

$x=\lim _{n\to \infty }x_{n}$.

Par exemple, la suite de mot finis $x_{n}=a^{n}b^{n}$ tend vers $a^{\omega }$.

Un cas particulier de cette situation se présente lorsque les mots $x_{n}$ sont chacun préfixe du mot suivant. Pourvu que la suite des longueurs tende vers l'infini, la limite $x$ est alors le mot infini dont les $x_{n}$ sont des préfixes.

Mots morphiques

Un morphisme $f:A^{*}\to A^{*}$ est prolongeable pour une lettre $a$ de $A$ si $a$ est un préfixe propre de $f(a)$, et si de plus, la suite des longueurs de itérés $f^{n}(a)$ tend vers l'infini lorsque $n$ tend vers l'infini.

Si $f:A^{*}\to A^{*}$ est prolongeable en $a$, il existe un mot non vide $u$ tel que $f(a)=au$. En itérant, on obtient l'expression :

$f^{n}(a)=auf(u)\cdots f^{n-1}(u)$

La suite de ces mots converge vers un mot infini noté $f^{\omega }(a)$ :

$f^{\omega }(a)=\lim _{n\to \infty }f^{n}(a)$

Ce mot est le mot infini engendré par $f$ en $a$. Un mot infini $x$ sur un alphabet $A$ est purement morphique s'il existe un morphisme $f:A^{*}\to A^{*}$ et une lettre $a$ dans $A$ tel que

$x=f^{\omega }(a)$

Un mot infini $y$ sur un alphabet $B$ 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 $\mu$ est défini par

${\begin{array}{rcl}a&\mapsto &ab\\b&\mapsto &ba\end{array}}$.

Il est prolongeable à la fois en la lettre $a$ et en la lettre $b$. Pour la lettre $a$, on obtient le mot infini de Thue-Morse :

$abbabaabbaababbabaababbaabbabaab\cdots$

et pour la lettre $a$, on obtient le mot opposé

$baababbaabbabaababbabaabbaababba\cdots$

— Le morphisme de Fibonacci est défini par

${\begin{array}{rcl}a&\mapsto &ab\\b&\mapsto &a\end{array}}$.

Il est prolongeable en $a$ ; en itérant, on obtient le mot infini :

$abaababaabaababaababa\cdots$.

Ces deux mots infinis sont donc purement morphiques.

— Le morphisme :

${\begin{array}{rcl}a&\mapsto &a1\\1&\mapsto &001\\0&\mapsto &0\end{array}}$

est prolongeable en $a$. En itérant, on obtient le mot infini :

$a1001000010000001000000001\cdots$

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 $a$ et $1$, 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 $\sigma$ est défini, pour tout mot infini

$x=a_{0}a_{1}\cdots a_{n}\cdots$,

par

$\sigma (x)=a_{1}\cdots a_{n}\cdots$.

La même définition vaut pour les mots infinis bilatères. Dans ce cas, $\sigma$ est une bijection. L'opérateur de décalage est une fonction continue.

Un système dynamique symbolique sur l'alphabet $A$ est un ensemble $S$ non vide de mots infinis sur $A$ qui est :

1. fermé pour l’opérateur de décalage $\sigma$ ;
2. 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 $A$ est une union finie d'ensembles de la forme

$KM^{\omega }$

où $K\subset A^{*}$ et $M\subset A^{+}$ sont des langages rationnels sur $A$. La famille des ensembles rationnels de mots infinis est fermée par union, et par produit à gauche par un langage rationnel sur $A$.

Exemples :

• Le langage $a^{*}b^{\omega }$ des mots sur $a$ et $b$ qui ont un nombre fini de $a$ est rationnel.
• Le langage $(b^{*}a)^{\omega }$ des mots sur $a$ et $b$ qui contiennent une infinité de $a$ est rationnel.

Bibliographie

• (en) Dominique Perrin et Jean Éric Pin, Infinite Words : Automata, Semigroups, Logic and Games, Amsterdam/Boston, Academic Press, 2004, 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 » (n^o 58), 1974, 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 » (n^o 2 500), 2002, viii+385 (ISBN 978-3-540-00388-5, lire en ligne).