Mot infini

Un mot infini sur un alphabet ${\displaystyle A}$ est une suite infinie

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

composée d'éléments de ${\displaystyle 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 ${\displaystyle A}$. On peut aussi voir le mot comme un produit infini de lettres, et on rencontre alors la notation

${\displaystyle 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 ${\displaystyle A^{\mathbb {N} }}$ ou ${\displaystyle A^{\omega }}$ l'ensemble des mots infinis sur ${\displaystyle A}$. On peut considérer aussi des mots infinis bilatères, indexés par ${\displaystyle \mathbb {Z} }$ au lieu de ${\displaystyle \mathbb {N} }$.

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle d(x,y)\leq \max(d(x,z),d(z,y))}$

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

${\displaystyle \ell (x,y)\geq \min(\ell (x,z),\ell (z,y))}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Un mot infini ${\displaystyle y}$ sur un alphabet ${\displaystyle B}$ est morphique s'il est l'image, par un morphisme littéral (lettre à lettre), d'un mot purement morphique.

L'opérateur de décalage ${\displaystyle \sigma }$ est défini, pour tout mot infini

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

par

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

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

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

1. fermé pour l’opérateur de décalage ${\displaystyle \sigma }$ ;
2. fermé pour la topologie.

La même définition vaut pour les mots infinis bilatères.

Un ensemble rationnel (on dit aussi langage rationnel ou ω-langage rationnel) de mots infinis sur un alphabet ${\displaystyle A}$ est une union finie d'ensembles de la forme

${\displaystyle KM^{\omega }}$

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

Exemples :

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

• (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).

• Portail des mathématiques
• Portail de l'informatique théorique