# Sur les ensembles de mots infinis engendrés par une grammaire algébrique

Maurice Nivat

<figure><img src="image_1.png" /></figure>

## To cite this version:

Maurice Nivat. Sur les ensembles de mots infinis engendrés par une grammaire algébrique. [Rapport de recherche] IRIA-RR-290, IRIA. 1978, pp.25. hal-04716547

HAL Id: hal-04716547

https://inria.hal.science/hal-04716547v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Dw-03935

RR290

RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

SUR LES ENSEMBLES
DE MOTS INFINIS
ENGENDRÉS PAR UNE
GRAMMAIRE ALGÉBRIQUE

Maurice NIVAT

Rapport de Recherche N° 290

Avril 1978

ESP
SUR LES ENSEMBLES DE MOTS INFINIS ENGENDRÉS PAR
UNE GRAMMAIRE ALGÉBRIQUE

Maurice Nivat

Résumé :

Dans cet article qui fait directement suite à l'article «Mots infinis engendrés par une grammaire algébrique» RAIRO Informatique Théorique II (1977) 311-327, nous définissons le concept d'adhérence. d'un langage de mots finis. Nous caractérisons parmi les ensembles de mots finis et infinis engendrés par une grammaire algébrique ceux qui peuvent l'être par une grammaire de Greibach réduite. Nous donnons un théorème de substitution qui a de nombreux corollaires.

Abstract :

This paper follows directly the previous paper «Mots infinis engendrés par une grammaire algébrique» RAIRO Informatique Théorique II (1977) 311-327. We define the concept of adherence of a language composed only of finite words. Among the sets of finite and infinite words which can be generated by an algebraic (context-free) grammar we characterize those which can be generated by a reduced grammar in Greibach normal form. We also give a substitution theorem which has a number of corollaries.
## Introduction

Nous avons défini en [4], paru ici-même, l'ensemble $L^ω(G, f)$ des mots infinis engendrés par une grammaire algébrique à partir d'un mot $f$ (l'axiome).

Ci dessous nous étudions les $ω$-langages algébriques, c'est à dire les langages de la forme $L^∞(G, f) = L^ω(G, f) \cup L(G, f)$ formés des mots finis et infinis engendrés par une grammaire algébrique. La notion essentielle est celle d'adhérence qui se relie immédiatement à celle de clôture [2] ou celle équivalente de limite [3]. Si la clôture d'une partie $L$ de $X^*$ est définie comme l'ensemble des mots infinis sur $X$ qui ont une infinité de facteurs gauches dans $L$, l'adhérence de $L$ est simplement la clôture de $FG(L)$, ensemble des facteurs gauches de mots de $L$.

Notre principal résultat (Théorème 6) caractérise les $ω$-langages algébriques qui peuvent être engendrés par une grammaire de Greibach réduite comme ceux qui satisfont la condition

$$L \cap X^ω = \mathrm{Adh}(L \cap X^*)$$

La nécessité de cette condition rend claire la différence qui existe entre $ω$-langages algébriques et langages algébriques ordinaires composés uniquement de mots finis : quand on met une grammaire algébrique sous forme de Greibach on modifie l'ensemble des mots infinis qu'elle engendre. Et ceci explique certains phénomènes étranges étudiés par R. Cohen et A. Gold [1] ou M. Linna [3].
L'essentiel de notre article est la démonstration d'un théorème de substitution (Théorème 1) que nous donnons complète car elle montre bien où sont les difficultés que rencontre la théorie des ω-langages algébriques : il ne suffit pas en effet de montrer l'existence d'une dérivation infinie il faut encore établir sa convergence c'est à dire montrer que l'ensemble des facteurs gauches terminaux des termes de la dérivation est infini.

Un corollaire de ce théorème est que tout mot infini produit par une dérivation quelconque l'est aussi par une dérivation gauche (en anglais "leftmost") et nos résultats se séparent là de ceux de [1]

L'algébricité de L qui est le plus petit langage fermé par facteur gauche dont l'adhérence soit égale à celle d'un langage algébrique L (Théorème 4) ouvre la voie à une étude des parties de $X^ω$ qui sont adhérences de langages algébriques, étude qui fait l'objet de travaux de l'auteur, à paraître.

Nos définitions sont celles de [4], à quelques détails près : nous avons trouvé commode de noter $\leq$ la relation "est un facteur gauche de" définie par

$$ \forall f,g \in X^*, f \leq g \Leftrightarrow \exists h \in X^* : g = fh $$

Ainsi $f<g$ signifie $f \leq g \land f \neq g$ que l'on lit $f$ est un facteur gauche propre de $g$ ou encore

$$ f<g \Leftrightarrow \exists h \in XX^* : g = fh $$

Nous notons $X^\infty = X^* \cup X^\omega$ et pour toute grammaire algébrique $G : \xi_i = p_i, i \in [N]$ et $f \in (X \cup \Xi)^*, L^\infty(G, f) = L^\omega(G, f) \cup L(G, f)$.

Nous appelons ω-langage algébrique toute partie $L^\infty$ telle qu'il existe une grammaire algébrique $G$ et un mot $f$ satisfaisant $L = L^\infty(G, f)$.

Si pour tout $t \in (X \cup \Xi)^*$ nous notons $\alpha(t)$ le plus long facteur gauche de $t$ qui soit dans $X^*$ (c'est à dire le plus long facteur gauche terminal) la dérivation $\delta = \langle t_n | n \in N_+ \rangle$ de $G$ est dite gauche si et seulement si pour tout $n \in N_+$, si $t_n = \alpha(t_n) \xi_{in}^\alpha \beta_{in}^\alpha$ il existe $m \in P_i$ tel que $t_{n+1} = \alpha(t_n) m \beta_{n+1}^\alpha$.

La démonstration du théorème 1 nous oblige maintenant à donner de nombreuses définitions concernant les arbres de dérivations finis et infinis.
# I - Arbres et arbres de dérivations

N_+ dénote l'ensemble des entiers strictement positifs.

Un domaine d'arbre est une partie A de (N_+)* qui satisfait les deux conditions

$$1. \quad \forall u \in (N_+)^*, n \in N_+, \text{ une } \epsilon \Rightarrow u \in A$$

$$2. \quad \forall u \in (N_+)^*, n, n' \in N_+, \\ \text{une } \epsilon \text{ et } n' < n \Rightarrow \text{un' } \epsilon \in A.$$

L'ensemble des arbres sur X, où X est un alphabet fini, est l'ensemble des applications partielles de (N_+)* dans X={ε} dont le domaine est un domaine d'arbre. On note X^A l'ensemble des arbres sur X.

Si σ est un arbre sur X, A(σ) désigne son domaine. Les éléments de A(σ) sont appelés sommets ou noeuds de l'arbre σ. Les sommets de A(σ) ∩ uN_+ sont dits fils du sommet u qui réciproquement est dit être leur père. Le sommet ε est appelé racine de l'arbre.

Si A est un domaine d'arbre, nous dirons que A' est un sous domaine d'arbre de A si et seulement si

- A' est un domaine d'arbre

- ∀u ∈ A' \cup N_+ \cap A' \neq ∅ \Rightarrow u \cup N_+ \cap A' = u \cup N_+ \cap A.

L'arbre σ' est dit sous arbre initial de σ, ce que l'on note σ' ⊂ σ si et seulement si :

- A(σ') est un sous domaine d'arbre de A(σ)

- σ' est la restriction de σ à A(σ') ce que l'on note σ' = σ|A(σ').

La relation "est un sous arbre initial de" est évidemment une relation d'ordre. Nous avons la

**Propriété 1** : Tout sous ensemble dirigé d'arbres, dirigé pour la relation "est un sous arbre initial de", admet une borne supérieure.

**Démonstration** : Un sous ensemble dirigé pour < est une partie Δ de X^A telle que
$$ \forall \sigma_1, \sigma_2 \in \Delta \quad \exists \sigma_3 \in \Delta \quad \text{tel que } \sigma_1 < \sigma_3 \text{ et } \sigma_2 < \sigma_3. $$

On note qu'une suite croissante <σ_n|n∈N> d'arbres est une partie dirigée de X^A.
Soit donc $\Delta$ une partie dirigée de $X^4$.

On vérifie d'abord que $A = \bigcup_{\sigma \in \Delta} A(\sigma)$ est un domaine d'arbre. En effet
$\underline{un} \in A \Rightarrow \underline{un} \in A(\sigma)$ on en déduit $n \in A$. De même $\underline{un} \in A$ et $n' < n$ impliquent $\underline{un} \in A(\sigma)$ pour
quelque $\sigma \in \Delta$ et $n' < n$ d'où $\underline{un}' \in A(\sigma)$ et par suite $\underline{un}' \in A$.

Maintenant si $\Delta$ est dirigé, $\sigma_1$ et $\sigma_2$ appartiennent à $\Delta$, $\underline{u} \in A(\sigma_1) \cap A(\sigma_2)$
on a $\sigma_1(u) = \sigma_2(u)$. En effet si $\sigma_3$ est tel que $\sigma_1 < \sigma_3$ et $\sigma_2 < \sigma_3$, $A(\sigma_1)$ et $A(\sigma_2)$
sont des sous domaines d'arbre de $A(\sigma_3)$ ce qui implique que pour tout
$\underline{u} \in A(\sigma_1) \cap A(\sigma_2)$, $\sigma_3(u)$ est défini et égal à $\sigma_1(u)$ et $\sigma_2(u)$.

D'où la borne supérieure $\text{Sup} \Delta$ : son domaine est $A(\text{Sup} \Delta) = \bigcup_{\sigma \in \Delta} A(\sigma)$
et pour tout $\underline{u} \in A(\text{Sup} \Delta)$, $(\text{Sup} \Delta)(u)$ est égal à la valeur commune de tous les $\sigma(u)$,
où $\sigma \in \Delta$ est tel que $\underline{u} \in A(\sigma)$. $\square$

Entre les sommets d'un arbre $\sigma$ nous avons les deux relations :

- $\underline{u} \leq \underline{u}'$ que l'on lit $\underline{u}$ est au dessus de $\underline{u}'$ ou $\underline{u}'$ est en dessous de $\underline{u}$ si
et seulement si $\underline{u}$ est facteur gauche de $\underline{u}'$. On note $\underline{u} < \underline{u}'$ la relation $\underline{u} \leq \underline{u}'$ et $\underline{u} \neq \underline{u}'$.

- $\underline{u} < \underline{u}'$ que l'on lit $\underline{u}$ "est à gauche" de $\underline{u}'$ si et seulement si

$$ \exists u_1, u_2, u_2' \in (\mathbb{N}_+)^* \text{ n}, n' \in \mathbb{N}_+ \text{ tels que } n < n' \text{ et } u = u_1, n u_2 \text{ et } u' = u_1, n' u_2' $$

On remarquera que la relation $(\leq \underline{u} < \underline{u}')$ est une relation d'ordre : c'est la
relation d'ordre lexicographique $\leq_{\ell}$ sur $(\mathbb{N}_+)^*$.

Si $\sigma$ est un arbre, $\underline{u} \in A(\sigma)$ un sommet, on vérifie immédiatement que
$A(\sigma:u) = \{v | uv \in A(\sigma)\}$ est un domaine d'arbre et l'on définit le sous arbre issu
de $\underline{u}$, noté $\sigma:u$ comme l'arbre de domaine $A(\sigma;u)$ donné par $(\sigma:u)(v) = \sigma(uv)$.

Nous aurons besoin de définir encore une espèce de sous-arbres.

Si $\underline{u} \in A(\sigma)$ l'ensemble

$\{v \in A(\sigma) | v \leq \underline{u} \text{ ou } v < \underline{u}\}$ est un domaine d'arbre, dont on remarquera que ce
n'est pas un sous-domaine d'arbre de $A(\sigma)$.

La restriction de $\sigma$ à ce domaine est notée $\text{SG}(\sigma, u)$ et appelée sous-arbre
à gauche de $\underline{u}$.

Il est facile d'établir que si $\sigma'$ est un sous arbre initial de $\sigma$ et si
$\underline{u} \in A(\sigma')$ alors $\text{SG}(\sigma', u)$ est un sous arbre initial de $\text{SG}(\sigma, u)$

Nous appelerons branche d'un arbre $\sigma$ toute suite de sommets tels que
chacun soit fils de celui qui le précède et le premier soit $\varepsilon$.

Ainsi $b = \langle u_1, \dots, u_n \rangle$ est une branche finie si et seulement si $u_1 = \varepsilon$ et
pour tout $i \in [(n-1)]$ $u_{i+1} \in u_i \cap N_+$. Le sommet $u_n$ est dit extrémité de la branche b
et il est clair qu'il existe une et une seule branche d'extrémité u pour tout
$u \in A(\sigma)$.

La branche $b = \langle u_n | n \in \mathbb{N}_+ \rangle$ est une branche infinie si et seulement si
$n_1 = \varepsilon$ et pour tout $i \in \mathbb{N}_+ \cup \{0\}$, $u_{i+1} \in u_i \cap \mathbb{N}_+$

Définissons maintenant la frontière et le feuillage d'un arbre σ.

La frontière de σ notée $\text{fr}(\sigma)$ est l'ensemble

$$ \text{fr}(\sigma) = \{u \in A(\sigma) \mid u \in \mathbb{N}_+ \cap A(\sigma) = \emptyset\} $$

Le feuillage de σ noté $\text{fg}(\sigma)$ est un mot de $X^*$ que l'on définit par récurrence pour tout σ de domaine fini de la façon suivante :

- si $A(\sigma) = \emptyset$, $\text{fg}(\sigma) = \varepsilon$

- si $A(\sigma) = \{\varepsilon\}$, $\text{fg}(\sigma) = \sigma(\varepsilon)$

- si $A(\sigma) \cap \mathbb{N} = [p]$

$$ \text{fg}(\sigma) = \text{fg}(\sigma:1) \text{fg}(\sigma:2) \cdots \text{fg}(\sigma:p) $$

Nous laisserons le soin au lecteur de vérifier les propriétés suivantes.

**Propriété 2** : Si $u_1, u_2, \dots, u_p$ est la suite ordonnée dans l'ordre lexicographique $\leq_\ell$ des sommets de $\text{fr}(\sigma)$ où $\sigma$ est un arbre fini alors

$$ \text{fg}(\sigma) = \sigma(u_1) \sigma(u_2) \cdots \sigma(u_p) $$

**Propriété 3** : Pour tout arbre de domaine fini $\sigma$, $\alpha, \beta \in X^*$, $x \in X$
la condition $\alpha \times \beta = \text{fg}(\sigma)$ implique l'existence d'une et une seule branche
$b = \langle u_1, \dots, u_n \rangle$ de $\sigma$ telle que

$$ \text{fg}(\text{SG}(\sigma, u_n)) = \alpha x $$

Par contre nous allons démontrer les deux propriétés suivantes

**Propriété 4** : Si $\sigma$ vérifie la condition

$$ \forall u \in A(\sigma) \quad \text{card} \left( \bigcup_{n \in \mathbb{N}} \cap A(\sigma) \right) < \infty $$

on dit alors que $\sigma$ est de type fini. Si $\sigma$ est infini et de type fini, $\sigma$ possède une branche infinie.

**Propriété 5** : Disons que la branche infinie $\langle v_n | n \in \mathbb{N} \rangle$ est à gauche de la branche infinie $\langle u_n | n \in \mathbb{N} \rangle$ si et seulement si $\forall n \in \mathbb{N} \ v_n \leq u_n$ ou $v_n < u_n$.

Alors si $\sigma$ est un arbre intini et de type fini il existe une branche
intinie plus à gauche que toutes les autres dite la branche infinie la plus à
gauche de $\sigma$.
**Démonstration** : La propriété 4 est une forme du lemme de Koenig que nous énonçons sous la forme suivante, qui nous a déjà servi en [4] et nous reservira plus loin.

**Lemme de Koenig** : Soit E un ensemble infini, R une relation sur E, une suite $A_1, A_2, \dots, A_n, \dots$ de parties finies non vides de E telles que
$$ - \bigcup_{i \le 1} A_i \text{ est de cardinalité infinie} $$

$$ - \forall n \ge 1, y \in A_{n+1} \exists x \in A_n : xRy $$

alors il existe une suite infinie d'éléments $a_1, a_2, \dots, a_n, \dots$ telle que
$$ - \forall n \in \mathbb{N}_+ \ a_n \in A_n \text{ et } a_n \supset a_{n+1}. $$

**Démonstration** : Si $\sigma$ est un arbre infini de type fini, définissons la suite des ensembles $A_n$ par

$$ A_n = A(\sigma) \cap \left( \bigcup_{k=0}^{n} (\mathbb{N}_+)^k \right) $$

qui est l'ensemble des sommets dits de hauteur inférieure où égale à k. Chacun de ces ensembles est fini et non vide.

En effet $A_0$ est fini. Et si $A_n$ est fini, $A_{n+1} = A_n \cup (\bigcup_{n \in A_n} (u\mathbb{N}_+ \cap A(\sigma)))$ est fini puisque $\sigma$ est de type fini. D'où l'on déduit par récurrence que $A_n$ est fini pour tout $n \in \mathbb{N}$.

Mais ceci entraine que $A_n$ aussi est non vide, pour tout n, puisque
$$ A_n = \emptyset \Rightarrow A_{n+1} = \emptyset \text{ et si } A_n \text{ était vide pour quelque } n \text{ l'arbre serait fini.} $$

Considérons alors la relation R définie par

$$ (u,v) \in R \Leftrightarrow v \in u\mathbb{N}_+ $$

Pour tout $v \in A_{n+1}$ il existe $u \in A_n$ tel que $(u,v) \in R$, if suffit de prendre u égal au facteur gauche de longueur n de v.

Le lemme de Koenig fournit alors le résultat. $\square$

Pour démontrer la propriété 5 on construit la branche infinie la plus à gauche de la manière suivante : disons que la branche $b = \langle u_n | n \in \mathbb{N} \rangle$ passe par le sommet u si et seulement si il existe $n \in \mathbb{N}$ tel que $u = u_n$.
Appelons alors $v_n$ le sommet le plus à gauche de $A_n$ par lequel passe une branche infinie de $\sigma$ supposé infini et de type fini. La suite $\langle v_n | n \in \mathbb{N} \rangle$ est une branche infinie, c'est à dire satisfait

$$ \forall n \in \mathbb{N} \ v_{n+1} \in v_{n+} $$

En effet $v_{n+1} \in v'N_+$ avec $v' <_g v_n$ implique que $v_n$ n'est pas le sommet le plus à gauche de $A_n$ par lequel passe une branche infinie et $v_{n+1} \in v'N_+$ avec $v_n <_g v'$ contredit l'hypothèse que $v_{n+1}$ est le sommet le plus à gauche de $A_{n+1}$ par lequel passe une branche infinie. $\square$

De la construction précédente découle facilement la

**Propriété 6** : Si $\sigma$ est un arbre infini de type fini, sa branche infinie la plus à gauche est égale à la suite ordonnée par $\le$ sommets de $A(\sigma)$ défini

$$ B = \{ u \in A(\sigma) \mid A(\sigma:u) \text{ est infini et } \forall u', u' <_g u \Rightarrow A(\sigma:u') \text{ est fini} \} $$

**Démonstration** : Si $b$ est la branche infinie la plus à gauche de $\sigma$, $b = \langle u_n | n \in \mathbb{N}_+ \rangle$ il est clair que pour tout $n, A(\sigma:u_n)$ est infini et pour tout $u'$ tel que $u' <_g u_n$ $A(\sigma:u')$ est fini. Et si au contraire $u \in A(\sigma)$ est un sommet tel que il existe $u' <_g u$ avec $A(\sigma:u')$ infini u n'appartient pas à la branche infinie la plus à gauche. $\square$

On retiendra que le sous-arbre issu de tout sommet à gauche de la branche infinie la plus a gauche est fini.

**Propriété 7** : Pour toute branche $b$ de l'arbre $\sigma \in X$ il existe un arbre minimum dans l'ensemble des sous-arbres initiaux de $\sigma$ qui contiennent la branche $b$.

**Démonstration** : Soit $b$ une branche infinie $b = \langle u_n | n \in \mathbb{N} \rangle$.

Appelons $b_n$ la branche finie $\langle u_1, \dots, u_n \rangle$.

Nous construisons par récurrence $\sigma_1, \dots, \sigma_n, \dots$ sous-arbres initiaux minimaux de $\sigma$ tels que $b_n$ soit une branche de $\sigma_n$ et $\sigma_1 < \sigma_2 < \dots < \sigma_n < \dots$

$$ \text{Pour } \sigma_1 \text{ on prend } A(\sigma_1) = \varepsilon \text{ et } \sigma_1(\varepsilon) = \sigma(\varepsilon) $$

$$ \text{Pour } n+1, \text{ en supposant construit } \sigma_n, \text{ on prend } A(\sigma_{n+1}) = A(\sigma_n) \cup (u_n N_+ \cap A(\sigma)) \\ \text{et } \sigma_{n+1} = \sigma |_{A(\sigma_{n+1})}. $$
Il est clair que $\sigma_n < \sigma_{n+1}$ et $\sigma_{n+1}$ est minimum puisque si $\tau$ contient la branche $b_{n+1}$ il contient la branche $b_n$ donc, par récurrence, $\sigma_n < \tau$. Et si $A(\tau)$ contient $u_{n+1} = u_n p$ il doit aussi contenir $u_n N_+ \cap A(\sigma)$ donc $A(\sigma_{n+1})$.

A la limite $\sup\{\sigma_n\}$ est minimum dans l'ensemble des sous-arbres qui contiennent la branche b. $\square$

### Arbres de dérivation d'une grammaire algébrique G.

Posons pour tout arbre $\sigma \in X^\sigma$ et $u \in A(\sigma)$

$$ \begin{gathered} \pi_\sigma(u) = \sigma(u1) \sigma(u2) \cdots \sigma(up) \text{ si} \\ [P] = A(\sigma) \cap uN_+ \end{gathered} $$

$\pi_\sigma(u)$ sera appelé descendance directe de $u$ dans $\sigma$.

Soit $G: \xi_i = P_i, i \in [N]$ une grammaire algébrique.

Un arbre $\sigma$ sur $(X \cup \Xi)$ est dit arbre de dérivation de $G$ si et seulement si

$$ \begin{gathered} - A(\sigma) \cap uN_+ \neq \emptyset \Rightarrow \sigma(n) \in \Xi \\ - q(u) = \xi_i \Rightarrow \begin{aligned}[t] \pi_\sigma(u) &= \varepsilon \\ \pi_\sigma(u) &\in P_i \end{aligned} \text{ ou} \\ \pi_\sigma(u) \in P_i \end{gathered} $$

Or, notera que tout arbre de dérivation de $G$ est de type fini. Nous dirons qu'un arbre de dérivation $\sigma$ de $G$ contient une dérivation $\delta = \langle t_1, \dots, t_n \rangle$ ou $\delta = \langle t_n | n \in N \rangle$ de $G$ si et seulement si il existe une suite croissante de sous-arbres initiaux $\sigma_1 < \sigma_2 < \dots < \sigma_n < \dots$ de $\sigma$ telle que

$$ - \forall i \in [n] \text{ (ou } \forall i \in N_+) \quad \text{fg}(\sigma_i) = t_i $$

$$ - \sup\{\sigma_n\} = \sigma $$

Nous avons les propriétés suivantes

**Propriété 8** : Pour toute dérivation finie ou infinie $\delta$ de $G$, d'origine $\xi_i \in \Xi$ il existe un arbre de dérivation $\sigma$ de $G$ qui contient $\delta$.

**Démonstration** : On construit $\sigma$ de la façon suivante :

$$ \text{soit } \delta = \langle t_1, \dots, t_n, \dots \rangle, \delta_n = \langle t_1, \dots, t_n \rangle. $$

On construit $\sigma_n$ qui contient $\delta_n$ de façon que $\sigma_n$ soit un sous-arbre initial de $\sigma_{n+1}$.

Pour $\sigma_1$ on prend l'arbre de domaine $\{\varepsilon\}$ tel que $\sigma_1(\varepsilon) = \xi_i$.
Si l'on suppose construit $\sigma_n$ et l'on suppose

$$t_n = \alpha \xi_j \beta, \quad t_{n+1} = \alpha m \beta \text{ pour quelque } m \in P_j$$

on sait par la propriété 3 qu'il existe une et une seule branche $b_n = \langle u'_n, \dots, u_n \rangle$ telle que

$$\mathrm{fg}(\mathrm{SG}(\sigma_n, u_n^p)) = \alpha \text{ et } \sigma(u_n^p) = \xi_j.$$

On construit alors $\sigma_{n+1}$ de domaine

$$A(\sigma_n) = \bigcup_n u_n^p [ |m| ] \quad \text{avec}$$

$$\sigma_{n+1}|_{A(\sigma_n)} = \sigma_n \quad \text{et} \quad \sigma_{n+1}(u_n^p h) = \lambda_h^p \text{ pour tout } h \in [m].$$

La notation $\lambda_h^p$ désigne la h$^{ième}$ lettre de m.

Il est clair que $\sigma_n < \sigma_{n+1}$ et $\sigma_{n+1}$ domine $\delta_{n+1}$.

La borne supérieure $\sup\{\sigma_n\}$ contient la dérivation $\delta$. $\square$

**Propriété 9** : Si $\sigma'$ est un sous-arbre initial fini de $\sigma$, où $\sigma$ est un arbre de dérivation de $G$, il existe une dérivation $\delta$ dans $G$ de $\sigma(\varepsilon)$ en $\mathrm{fg}(\sigma')$ contenue dans $\sigma$.

**Démonstration** : On fait une récurrence sur $\mathrm{card} \ A(\sigma')$.

Si $\mathrm{card} \ A(\sigma') = 1$, $A(\sigma') = \{\varepsilon\}$ c'est clair.

Sinon considérons $A(\sigma')$. Il existe dans $\mathrm{fr}(\sigma')$, qui est fini, des mots de longueur maximale c'est à dire des mots u tels que $v \in \mathrm{fr}(\sigma') \Rightarrow |v| \le |u|$.

Prenons en un, soit $u = u'p$, $u' \in (\mathbb{N}_+)^*$, $p \in \mathbb{N}_+$.

Il existe une dérivation de $\xi_i$ en $\mathrm{fg}(\sigma'')$ où $\sigma'' = \sigma|(A(\sigma')\setminus u'\mathbb{N}_+)$ contenue dans $\sigma$ soit $\delta = \langle t_1, \dots, t_{k+1} \rangle$. Mais si $\sigma(u') = \xi_j$ on a $t_{k+1} = \mathrm{fg}(\sigma'') = \alpha \xi_j \beta$ pour quelque $\alpha, \beta$, et si l'on pose $t_{k+2} = \mathrm{fg}(\sigma') = \alpha \pi_\sigma(u')\beta$ il est clair que $\langle t_1, \dots, t_{k+2} \rangle$ est une dérivation de $\xi_i$ en $\mathrm{fg}(\sigma')$ contenue dans $\sigma$. $\square$
## II - Théorème de substitution

Nous devons d'abord définir la substitution.

Soit $u \in (X \cup \Xi)^\omega$ et $\tilde{Q} = \langle Q_1, \dots, Q_N \rangle$ sur $N$-vecteur de parties de $X^*$.

Nous notons $u[\tilde{Q}/\tilde{\xi}]$ la substitution de $\tilde{Q}$ à $\tilde{\xi}$ dans $u$ définie par

$$ - u[\tilde{Q}/\tilde{\xi}] \subset X^\omega $$

$$ - \forall v \in X^\omega, v \in u[\tilde{Q}/\tilde{\xi}] \text{ si et seulement si il existe une suite d'entiers } p_n \\ \text{telle que} $$

$$ p_n \xrightarrow{n \to \infty} \infty \quad \text{et} \quad \forall n \ v[p_n] \in u[n][\tilde{Q}/\tilde{\xi}]. $$

La notation $u[n]$ désigne le facteur gauche de longueur $n$ de $u$.
Une définition équivalente est donnée par le

**Lemme 1 :** Soit $u \in (X \cup \Xi)^\omega$ le mot

$$ u = \sigma_1 \xi_{i_1} \alpha_2 \xi_{i_2} \cdots \alpha_p \xi_{i_p} \alpha_{p+1} \cdots $$

où pour tout $p \in \mathbb{N}_+$, $\alpha_p \in X^*$ et $\xi_i \in \Xi$.

Alors le mot $v \in X^\omega$ appartient à $u[\tilde{Q}/\tilde{\xi}]$ si et seulement si il existe $h_1, h_2, \dots, h_p, \dots$ tels que

$$ v = \alpha_1 h_1 \alpha_2 h_2 \cdots \alpha_p h_p \alpha_{p+1} \cdots $$

$$ \text{et } \forall p \in \mathbb{N}_+, h_p \in Q_i. $$

**Démonstration :** Dans un sens c'est évident puisque $\alpha_1 h_1 \cdots \alpha_p h_p \in \alpha_1 \xi_1 \cdots \alpha_p \xi_i [\tilde{Q}/\tilde{\xi}]$ et que $v = \alpha_1 h_1 \cdots \alpha_p h_p \alpha_{p+1} \cdots$ implique que

$$ |\alpha_1 h_1 \cdots \alpha_p h_p| \xrightarrow{\infty} \infty \text{ si } p \to \infty. $$

Réciproquement, soit $p_n$ la suite telle que

$$ v[p_n] \in u[n][\tilde{Q}/\tilde{\xi}] $$

Considérons la suite des entiers $n_1, \dots, n_k, \dots$ tels que

$$ u[n_k] = \alpha_1 \xi_{i_1} \cdots \alpha_k \xi_{i_k} $$
Pour tout $k \in \mathbb{N}_+$, il existe $h_1^{(k)}, \dots, h_k^{(k)}$ tels que $v[p_{n_k}] = \alpha_1 h_1^{(k)} \cdots \alpha_k h_k^{(k)}$

Une simple application du lemme de Koenig permet d'établir qu'il existe alors $h_1, \dots, h_k, \dots$ tels que

$$v[p_{n_k}] = \alpha_1 h_1 \cdots \alpha_k h_k \quad \text{pour tout } k. \quad \square$$

On remarquera que $u[\vec{Q}/\vec{\xi}]$ ne contient pas les mots finis qui pourraient provenir de la substitution telle qu'elle est traditionnellement définie.

Nous pouvons alors énoncer le

**Théorème 1** : Soit $G$ la grammaire algébrique $\xi_i = P_i$, $i \in [N]$.

Soit $\bar{G}$ la grammaire algébrique en les variables $\Xi = \{\xi_1, \dots, \bar{\xi}_N\}$ sur l'alphabet terminal $X \cup \Xi$ définie par

$$\bar{\xi}_i = \bar{P}_i, \quad i \in [N] \quad \text{où}$$

$$\bar{P}_i = \{ \alpha \bar{\xi}_j | \alpha \in (X \cup \Xi)^*, \bar{\xi}_j \in \Xi, \alpha \bar{\xi}_j (X \cup \Xi)^* \cap P_i \neq \emptyset \}.$$

$$\text{Alors pour tout } i \in [N], L^\omega(G, \xi_i) = L^\omega(\bar{G}, \bar{\xi}_i) \quad [\overrightarrow{L(\bar{G})}/\bar{\xi}]$$

**Démonstration** : On démontre d'abord l'inclusion $\subset$.

Considérons une dérivation infinie terminale $\delta = \langle t_n | n \in \mathbb{N}_+ \rangle$ à partir de $t_1 = \xi_i$ dans $G$. Supposons qu'elle engendre le mot $W \in X^\omega$ où $W = \lim_{n \to \infty} \alpha(t_n)$, $\alpha(t_n)$ étant le plus long facteur gauche terminal de $t_n$.

Soit $\sigma$ un arbre de dérivation de $G$ contenant $\delta$. Soit $b = \langle u_n | n \in \mathbb{N}_+ \rangle$ sa branche infinie la plus à gauche. Nous notons $\sigma_n$ le sous-arbre initial minimum de $\sigma$ tel que $u_n \in A(\sigma_n)$ et $\sigma' = \text{Sup}\{\sigma_n\}$.

La démonstration réside essentiellement dans la considération des arbres $\bar{\sigma}_n$ ainsi contruits :

si $\tau$ est un sous-arbre initial de $\sigma$, nous définissons

$$A(\bar{\tau}) = \{ v \in A(\tau) \mid \exists n \in \mathbb{N}_+ : v \le u_n \text{ ou } v < g u_n \}$$

$$\bar{\tau}(v) = \bar{\tau}(\overline{v}) \quad \text{pour tout } v \in b$$

$$\bar{\tau}(v) = \tau(v) \quad \text{pour tout } v \in b.$$

Intuitivement pour obtenir $\bar{\tau}$ on supprime toute la partie de $\tau$ qui est strictement à droite de la branche b et l'on barre les étiquettes des sommets qui sont sur b.
Nous pouvons établir plusieurs propriétés

**Lemme 2** : Pour tout $n \in \mathbb{N}_+$

$fg(\text{SG}(\sigma, u_n)) = \bar{w}_n \sigma(u_n)$ où $w_n \in (X \cup \Xi)^*$ et $\sigma(u_n) \in \Xi$ et

$fg(\text{SG}(\bar{\sigma}_n, u_n)) = \bar{w}_n \bar{\sigma}(u_n)$ où $\bar{w}_n \in (X \cup \Xi)^*$.

Enfin $w_n \in \bar{w}_n [\overrightarrow{\hat{L}(G)} / \xi]$

Dans cette écriture $\hat{L}(G, \xi_i) = \{f \in (X \cup \Xi)^* | \xi_i \stackrel{*}{\equiv} G f\}$

**Démonstration** : si $n=1$ il n'y a rien à démontrer.

Nous faisons une récurrence sur $n$.

Supposons $u_{n+1} = u_n p$ pour $p \in \mathbb{N}_+$. Nous pouvons écrire

$$A(\text{SG}(\sigma, u_{n+1})) = \{v \in A(\sigma) \mid v \le u_{n+1} \text{ ou } v < g u_{n+1}\}$$

$$= A(\text{SG}(\sigma, u_n)) \cup \{v \in A(\sigma) \mid u_n < v \text{ et } v < g u_{n+1}\} \cup \{u_{n+1}\}$$

$$= A(\text{SG}(\sigma, u_n)) \cup A(\sigma:u_n 1) \cup \dots \cup A(\sigma:u_n (p-1)) \cup \{u_{n+1}\}$$

En remarquant que les termes de cette union sont disjoints et que les éléments de chacun d'eux précédent dans l'ordre lexicographique les éléments du terme suivant, nous déduisons

$$fg(\text{SG}(\sigma, u_{n+1})) = w_{n+1} \sigma(u_{n+1}) \text{ et}$$

$$w_{n+1} = w_n \quad fg(\sigma:u_n 1) \cdots fg(\sigma:u_n (p-1))$$

De façon similaire, en se reportant à la définition de $\sigma_n$ et $\bar{\sigma}_n$ :

$$fg(\text{SG}(\bar{\sigma}_{n+1}, u_{n+1})) = \bar{w}_{n+1} \overline{\sigma(u_{n+1})} \text{ et}$$

$$w_{n+1} = \bar{w}_n \sigma(u_n 1) \cdots \sigma(u_n (p-1)).$$

Les deux suites $w_n$ et $\bar{w}_n$ sont ainsi des suites croissantes pour l'ordre $\le$. La propriété de b d'être la branche infinie la plus à gauche entraîne que pour $i = 1, \dots, p-1$ $A(\sigma:u_n i)$ est fini puisque $u_n i < g u_{n+1}$. D'où $fg(\sigma:u_n i) \in \hat{L}(G, \sigma(u_n i))$ puisque $fg(\sigma:u_n i)$ est un mot de $(X \cup \Xi)^*$.

Par récurrence nous obtenons bien $w_n \in \bar{w}_n [\overrightarrow{\hat{L}(G)} / \xi]$. $\square$
Une autre remarque essentielle est

**Lemme 3** : Si la suite $\overline{w}_n$ est stationnaire il en est de même de la suite $w_n$.

**Démonstration** : En effet la suite $\overline{w}_n$ est stationnaire si et seulement si à partir d'un certain $n_0$, $u_{n+1} = u_n$ pour tout $n \ge n_0$.

L'identité ci-dessus montre qu'alors $w_n$ est aussi stationnaire. $\square$

La démonstration s'achève par une suite de remarques.

La suite $w_n$ n'est pas stationnaire : en effet la dérivation $\delta$ est terminale ce qui implique que pour tout $n$

$w[n] \le fg(\tau_n)$ pour quelque sous arbre initial $\tau_n$ de $\sigma$.

Or si $u_p$ est le sommet où la branche infinie b rencontre la frontière de $\tau_n$ nous avons

$$ \alpha(fg(\tau_n)) \le fg(\sigma, u_p). $$

Il s'ensuit que les mots $w_n$ contiennent des facteurs gauches terminaux de longueur aussi grande que l'on veut. Comme ils forment une suite croissante pour $\le$ cela implique qu'ils sont tous dans $X^*$.

On peut alors remplacer la relation

$$ w_n \in \overline{w}_n [\overrightarrow{L(G)/\xi}] \quad \text{pour la relation} \\ w_n \in \overline{w}_n [\overrightarrow{L(G)/\xi}] $$

De fait que cette relation est satisfaite pour tout $n$ et que la suite des $\overline{w}_n$ n'est pas stationnaire on déduit que :

1 - la suite des $\overline{w}_n$ a une limite quand $n \to \infty$, notons la $\overline{w}$, et $\overline{w} \in (X \cup \Xi)^\omega$

2 - $w \in \overline{w}[L(\overline{G})/\overline{\xi}]$.

Or le mot $\overline{w}$ est engendré par une dérivation infinie terminale dans $\overline{G}$, précisemment la dérivation

$$ <fg(SG(\overline{\sigma_n}, u_n)), n \in \mathbb{N}_+ > $$

que cette suite soit une dérivation est immédiat par la relation établie plus haut :

$$ fg(SG(\overline{\sigma_{n+1}}, u_{n+1})) = \overline{w}_n \sigma(u_n 1) \cdots \sigma(u_n (p-1)) \overline{\sigma}(u_n p) $$

$$ \text{où } fg(SG(\overline{\sigma_n}, u_n)) = \overline{w}_n \overline{\sigma(u_n)}. $$
Qu'elle soit terminale et engendre $\bar{w} = \lim_{n \to \infty} \bar{w}_n$ ne l'est pas moins par la remarque que le plus long facteur de $fg(\overline{SG}(\bar{\sigma}_n, u_n))$ qui soit dans $(XU\Xi)^*$ est précisément $\bar{w}_n$ et le fait que la suite $w_n$ n'est pas stationnaire.

Nous avons établi la première inclusion. ☐

Etablissons l'inclusion inverse :

Soit $w \in L^\omega(\bar{G}, \bar{\xi}_i) [L(\hat{G}) / \hat{\xi}]$.

Soit $\bar{w} \in L^\omega(\bar{G}, \bar{\xi}_i)$ un mot tel que $w \in \bar{w}[L(\hat{G}) / \hat{\xi}]$.

Nous pouvons écrire $\bar{w} = \alpha_0 \xi_{i_1} \alpha_1 \xi_{i_2} \cdots \alpha_{n-1} \xi_{i_n} \alpha_n \cdots$ et

$w = \alpha_0 h_1 \alpha_1 h_2 \cdots \alpha_{n-1} h_n \alpha_n \cdots$ avec $h_n \in L(G, \xi_{i_n})$.

Considérons une dérivation infinie terminale de $\bar{\xi}_i$ en $\bar{w}$ dans $\bar{G}$, soit $t_1 = \bar{\xi}_1, t_2, \cdots, t_p, \cdots$. La grammaire $\bar{G}$ étant linéaire à droite on peut écrire pour tout $p \in \mathbb{N}_+$

$$t_p = u'_p \bar{\xi}_i \quad \text{avec } u'_p \in (XU\Xi)^* \text{ et } u'_p \le \bar{w}$$

Appelons $u_p$ le facteur gauche de $w$ obtenu en substituant aux occurrences de non terminaux $\xi_i, \dots, \xi_{i_k}$ dans $u'_p$ les mots $h_1, \dots, h_k$ correspondants.

Supposons connue une dérivation gauche $\delta_p$ de $\xi_i$ en un mot $u_p \xi_i v_p$ : nous construisons $\delta_{p+1}$ prolongeant $\delta_p$, dérivation gauche de $\xi_i$ en $u_{p+1} \xi_i v_{p+1}$.

Nous avons puisque $\langle t_n \rangle$ est une dérivation de $\bar{G}$, $u'_{p+1} = u'_p m'_{p+1}$ avec $m'_{p+1} \bar{\xi}_i \in \bar{p}_{i_p}$

Il existe ainsi $n'_{p+1}$ tel que $m'_{p+1} \xi_i \in P_i$ d'où

$$u_p \xi_i v_p \xrightarrow{G} u_p m'_{p+1} \xi_i \in P_{p+1}$$

Or $u_{p+1} = u_p m'_{p+1}$ où $m'_{p+1}$ est obtenu en substituant aux occurrences de non-terminaux $\xi_i, \dots, \xi_{i_k}$ dans $m'_{p+1}$ les $h_i, \dots, h_{i_k}$ correspondants.

Il existe une dérivation gauche de $\xi_i$ en $h_n$ dans $\bar{G}$ pour tout $n$ donc aussi une dérivation gauche de $m'_{p+1}$ en $m_{p+1}$, donc enfin une de $u_p \xi_i v_p$ en $u_{p+1} \xi_i \in P_{p+1} v_p$.
La dérivation $\delta_{p+1}$ est la dérivation $\delta_p$ prolongée de cette dérivation gauche de $u_p \xi_i v_p$ en $u_{p+1} \xi_i v_{p+1}$.

La suite croissante de dérivations $\delta_1, \delta_2, \dots, \delta_p, \dots$ a une limite $\delta$ qui est une dérivation infinie gauche et terminale de $\xi_i$ en w dans G. Ce qui établit le théorème. $\square$

Nous avons aussi établi la

**Propriété 10** : Pour toute grammaire algébrique G, tout non terminal $\xi_i$ et tout mot infini $w \in L^\omega(G, \xi_i)$ il existe une dérivation infinie terminale gauche de $\xi_i$ en w dans G.

### III - Adhérences de langages algébriques

Si A est une partie de $X^*$ on définit $A^\omega$ de la façon suivante :

- $A^\omega \subset X^\omega$ et pour tout $u \in X^\omega$ on a
  $u \in A^\omega \Leftrightarrow$ il existe une suite croissante d'entiers $p_1, p_2, \dots, p_n, \dots$ telle que $p_n \xrightarrow{n \to \infty} \infty$ et $u[p_n] \in A^n$.

On écrit un peu improprement $A^\omega = \{a_1 a_2 \dots a_n \dots | a_n \in A\}$ en sous entendant que $a_n$ est non nul pour une infinité de n.

Le théorème de substitution a de nombreuses conséquences.

La première est le

**Théorème 2** : Tout $\omega$-langage algébrique, $L = L^\omega(G, \xi_i)$ peut se mettre sous la forme
$$L = \bigsqcup_{k=1}^{p} L_k (L'_k)^\omega$$

où les $L_k$ et $L'_k$ sont des langages algébriques

La démonstration repose essentiellement sur le

**Lemme 4** : Si G est une grammaire algébrique linéaire à droite satistaisant pour
tout $i \in [N]$, $P_i \subset X^* \Xi$ alors pour tout $i \in [N]$, $L^\infty(G, \xi_i)$ est contenu dans $X^\omega$ et
se met sous la forme

$$
L^{\infty}(G, \xi_i) = \bigsqcup_{k=1}^{p} R_k (R'_k)^{\omega}
$$

**Démonstration** : Celle que nous donnons n'est qu'une esquisse de preuve, une démonstration rigoureuse se trouve dans l'ouvrage d'Eilenberg [2]. Le résultat est originellement dû à Mac Naughton.

Considérons d'abord la simple grammaire

$\xi = A\xi$

Il est clair qu'elle engendre $A^\omega = \{a_1 a_2 \cdots a_n \cdots | a_n \in A\}$.

Considérons la grammaire

$$
G \quad \left\{
\begin{array}{l}
\xi_1 = A_{11} \quad \xi_1 + A_{12} \quad \xi_2 \\
\xi_2 = A_{21} \quad \xi_1 + A_{22} \quad \xi_2
\end{array}
\right.
$$

Encore clairement on a

$$
L^{\omega}(G, \xi_1) = (A_{11})^* A_{12} L(G, \xi_2) + (A_{11})^{\omega}
$$

en séparant dans l'ensemble des dérivations infinies à partir de $\xi_1$ celles
qui ne contiennent jamais $\xi_2$ et les autres.

On en tire

$$
L(G, \xi_2) = A_{21} A_{11}^* A_{12} L(G, \xi_2) + A_{22} L(G, \xi_2) + A_{21} (A_{11})^\omega
$$

qui se résoud en

$$
L(G, \xi_2) = (A_{22} A_{11}^* A_{12} + A_{22}) * A_{21} (A_{11})^\omega + (A_{21} A_{11}^* A_{12} + A_{22})^\omega
$$

formule que l'on peut aussi établir à priori en séparant les dérivations intinies
qui contiennent $\xi_2$ une infinité de fois et les autres.

Ce raisonnement peut être appliqué, par récurrence, à toute grammaire
linéaire à droite, c'est à dire de la forme

$$
\xi_i = \sum_{j=1}^{N} A_{ij} \xi_j , i \in [N]
$$

et conduit au résultat cherché. □
Le théorème 2 découle immédiatement du théorème 1 et de la propriété puisque

$$L^\omega(G, \bar{\xi}_i) = L^\omega(\bar{G}, \bar{\xi}_i) [\vec{L}(\vec{G}) / \vec{\xi}]$$

où $\bar{G}$ est une grammaire linéaire à droite.

$$ 
\begin{align*}
\text{Ainsi } L^\omega(\bar{G}, \bar{\xi}_i) &= \left\lfloor \sum_{k=1}^{P} R_k (R_k')^\omega \right\rfloor \text{ et} \\
L^\omega(G, \xi_i) &= \left( \left\lfloor \sum_{k=1}^{P} R_k (R_k')^\omega \right\rfloor [\vec{L}(\vec{G}) / \vec{\xi}] \right. \\
&\qquad \left. = \left\lfloor \sum_{k=1}^{P} R_k [\vec{L}(\vec{G}) / \vec{\xi}] (R_k' [\vec{L}(\vec{G}) / \vec{\xi}])^\omega \right\rfloor \right)
\end{align*}
$$

La substitution algébrique $[L(\vec{G})/\vec{\xi}]$ applique les rationnels $R_k$ et $R_k'$ sur des langages algébriques $L_k$ et $L_k'$. $\square$

**Exemple** : On prend $G : \xi = a\xi\xi + b$, grammaire qui engendre comme langage de mots finis le langage de Lukasiewicz

$$L = \{f \in \{a,b\}^* \mid |f|_a = |f|_b - 1 \text{ et } f' < f \Rightarrow |f'|_a \ge |f'|_b\}$$

Le langage de mots infinis engendré par $G$ s'obtient en considérant

$$\bar{G} : \bar{\xi} = a\bar{\xi} + a\xi\bar{\xi}$$

qui engendre $L^\omega(\bar{G}, \bar{\xi}) = (a+a\xi)^\omega$.

$$ 
\begin{align*}
D'\text{où } L^\omega(G, \xi) &= (a+a\xi)^\omega [L/\xi] \\
&= (a/aL)^\omega.
\end{align*}
$$

On montrera plus loin que ce langage est aussi

$$\{u \in X^\omega | u' < u \Rightarrow |u'|_a \ge |u'|_b\}$$

**Remarque** : Avec les définitions qui sont les nôtres la réciproque du lemme 4 n'est pas vérifiée. Ainsi $a^*b^\omega$ n'est engendré par aucune grammaire linéaire à droite telle que $P_i \subset X^*\Xi$ pour tout $i \in [N]$.

Supposons en effet qu'il en soit ainsi et considérons une dérivation infinie de $\xi_i$ en $a^n b^\omega$, soit $t_1 = \xi_i, t_2, \dots, t_n \dots$. On peut écrire pour tout $n$ $t_n = u_n \xi_i$ et pour tout $n<p$ on a $u_n \le u_p$ et si $u_p = u_n v, \xi_i, \xi_j$ $\stackrel{*}{\sim}_G v \xi_i$. Si l'on prend n assez grand on trouvera certainement n et p tels que $n<p$, $u_n \le u_p \le a^n$ et $\xi_i = \xi_i$. D'où une dérivation $\xi_i, \xi_j \stackrel{*}{\sim}_G a^\ell \xi_i$. Mais si une telle dérivation existe, il existe une dérivation infinie de $\xi_i$ en $a^\omega$ dans G. $\square$
Nous définissons maintenant l'adhérence d'un langage.

**Ref 1** - Pour toute partie $L \subset X^\infty$ nous appelons adhérence de L et notons $\text{Adh}(L)$

l'ensemble des mots infinis u de $X^\omega$ tels que tous leurs facteurs gauches sont facteurs gauches d'un mot de L.

**Def 2** - La partie $L$ de $X$ est dite amène si et seulement si le sous-ensemble
$L^{\text{inf}} = L \cap X^\omega$ des mots infinis de $L$ est l'adhérence de l'ensemble
$L^{\text{fin}} = L \cap X^*$ des mots finis de $L$.

**Remarque :** La clôture $\overline{\mathcal{A}}$ d'un ensemble $\mathcal{A}$ de $X^*$ étant définie comme dans l'ouvrage d'Eilenberg [2] connue

$$ \overline{\mathcal{A}} = \{u \in X^\omega | \text{card}\{n | u[n] \in \mathcal{A}\} = \infty\} $$

on a immédiatement que pour $L \subset X^*$

$$ \text{Adh}(L) = \overline{\text{FG}(L)} $$

On remarquera que $\overline{\mathcal{A}^*} = \{u \in X^\omega | \text{card}\{n | u[n] \in \mathcal{A}^*\} = \infty\}$ n'est pas égal à $\mathcal{A}^\omega$
comme le montre l'exemple suivant :

**Exemple :**

$$ A = ab^* \qquad A^\omega = \{ab^{n_1} ab^{n_2} \cdots ab^{n_p} \cdots | n_1, n_2, \cdots, n_p \in \mathbb{N}\} $$

$$ \text{et } \overline{\mathcal{A}^*} = \mathcal{A}^\omega \cup \{ab^{n_1} ab^{n_2} \cdots ab^{n_p} \mid n_1, n_2, \cdots, n_p \in \mathbb{N}\} $$

D'une manière générale on a

$$ \overline{\mathcal{A}^*} = \mathcal{A}^{*\overline{\mathcal{A}}} \cup \mathcal{A}^\omega $$

Nous pouvons établir tout de suite la

**Propriété 11 :** Soit $L \subset X^*$ et $\mathcal{L}$ le langage
$$ \mathcal{L} = \{u \in X^* | \text{card}\{v \in X^* | uv \in L\} = \infty\} $$

$$ \text{Alors } \mathcal{L} = \text{FG}(\text{Adh}(L)) \text{ et } \text{Adh}(\mathcal{L}) = \text{Adh}(L). $$
**Démonstration** : Soit $u \in \text{Adh}(L)$ et $u' = u[n]$ un de ses facteurs gauches. Pour tout $p \in N_+$, $u' \le u[n+p]$ et il existe $v_{n+p}^*$ tel que $u[n+p]v_{n+p}^* \in L$.

D'où $u(n+1) \cdots u(n+p) v_{n+p}^* \in \{v' | u'v' \in L\}$ et ce dernier ensemble est infini.

Réciproquement si $\text{card}\{v|uv \in L\} = \infty$ on peut construire un mot $w \in \text{Adh}(L)$ tel que $u<w$. L'alphabет X étant comme toujours supposé fini $\{v|uv \in L\} \cap X^*$ est infini pour un moins un $x \in X$ soit $x_1$. Cela s'écrit card $\{v|ux_1^*, v \in L\} = \infty$ et permet de trouver $x_2$ tel que $\{v|ux_1^*, v \in L\} \cap x_2^*$ soit infini ou encore card $\{v|ux_1^*, x_2, v \in L\} = \infty$.

On peut ainsi construire une suite croissante $u, ux_1^*, ux_1^*, x_1, \dots$ dont la limite est un mot infini w de l'adhérence de L qui a u comme facteur gauche.

$L^{\circ}$-égalité $\text{Adh}(L) = \text{Adh}(L)$ se vérifie immédiatement. []

Les facteurs gauches $u$ de mots de $L$ qui ont la propriété que card $\{v|uv \in L\} = \infty$ sont dit infiniment complétables. Le langage $L$ sera dit intérieur de $L$.

Dans une étude des langages de mots infinis qui sont adhérence d'un langage algébrique, on est amené à utiliser constamment l'intérieur d'un langage algébrique. Nous allons établir le

**Théorème 4** : L'intérieur de tout langage algébrique est un langage algébrique.

Mais auparavant nous devons établir une importante propriété des langages de mots infinis engendrés par des grammaires de Greibach.

**Théorème 5** : Si la grammaire algébrique $G : \xi_i = P_i$, $i \in [N]$ est de Greibach et réduite alors pour tout $i \in [N]$, le langage $L^{\infty}(G, \xi_i)$ est amène c'est à dire

$$L^{\omega}(G, \xi_i) = \text{Adh}(L(G, \xi_i))$$

**Démonstration** : Rappelons que $G$ est de Greibach ssi pour tout $i \in [N]$, $P_i \in X(X \cup \Xi)^*$ et que $G$ est réduite ssi pour tout $i$, $L(G, \xi_i) \neq \emptyset$.
Disons que la dérivation gauche $\delta = \langle t_n | n \in [k] \rangle$

- dépasse le mot $g$ de $X^*$ ssi $g \le \alpha(t_k)$

- dépasse juste $g$ ssi $\alpha(t_{k-1}) < g \le \alpha(t_k)$.

Il est clair que si la dérivation $\delta = \langle t_n | n \in [k] \rangle$ dépasse $g$, il existe $k' \le k$ tel que $\delta' = \langle t_n | n \in [k'] \rangle$ dépasse juste $g$.

Si la grammaire $G$ est de Greibach, l'ensemble des dérivations gauches qui dépassent juste $g$ est fini pour tout $g$. En effet, si $\delta = \langle t_n | n \in [k] \rangle$ est gauche et dépasse juste $g$ on a $\alpha(t_{k-1}) < g$ donc $|\alpha(t_{k-1})| < |g|$. Or $\delta$ étant gauche et $G$ de Greibach $|\alpha(t_{k-1})| > k-1$ d'où $k \le |g|$.

Montrons alors que $L^\omega(G, \xi_i) \subset \text{Adh}(L(G, \xi_i))$ si $G$ est réduite : il suffit de montrer que si $\delta = \langle t_n | n \in N_+ \rangle$ est une dérivation infinie terminale d'origine $\xi_i$ et $u \le \alpha(t_n)$ il existe $v$ tel que $uv \in L(G, \xi_i)$. Or $G$ étant réduite pour tout mot $t \in (X \cup \Xi)^*$, $L(G, t) \ne \emptyset$ donc il existe $w \in L(G, t_n)$. On a bien $w \in L(G, \xi_i)$ et $u \le w$. L'inclusion inverse $\text{Adh}(L(G, \xi_i)) \subset L^\omega(G, \xi_i)$ se démontre en utilisant le lemme de Koenig.

Soit $u \in \text{Adh}(L(G, \xi_i))$ et pour tout $n$, $\Delta_n$ l'ensemble des dérivations gauches qui dépassent juste $u[n]$. Nous avons vu que $\Delta_n$ est fini et que pour tout $\delta \in \Delta_{n+1}$ il existe $\delta'$ dans $\Delta_n$ tel que $\delta$ prolonge $\delta'$. $\Delta_n$ est aussi non vide puisque si $v_n$ est tel que $u[n]v_n \in L(G, \xi_i)$ il existe une dérivation gauche de $\xi_i$ en $u[n]v_n$ qui dépasse $u[n]$. Appliquant le lemme de Koenig on construit alors une suite infinie de derivations $\delta_n$ telles que $\delta_n \in \Delta_n$ et $\delta_{n+1}$ prolonge $\delta_n$ pour tout $n$. La limite $\delta = \lim_{n \to \infty} \delta_n$ est une dérivation infinie gauche terminale de $\xi_i$ en $u$ dans $G$. $\square$

Le théorème 5 admet une réciproque

**Théorème 6** : Pour tout $\omega$-langage algébrique amène $L$ il existe une grammaire de Greibach réduite $G'$ telle que

$$L^\omega(G, \xi_i!) = L\{\epsilon\}$$

**Démonstration** : Supposons $L = L^\omega(G, \xi_i)$ pour quelque grammaire algébrique $G$ et $L$ amène qui se traduit par

$$L^\omega(G, \xi_i) = \text{Adh}(L(G, \xi_i))$$
Il est bien connu qu'on peut construire une grammaire de Greibach réduite $G'$ telle que

$$L(G', \xi') = L(G, \xi_i) \setminus \{\epsilon\}$$

Par le théorème 5 on a alors

$$L^{\omega}(G', \xi_i') = \mathrm{Adh}(L(G', \xi_i'))$$

donc aussi

$$L^{\omega}(G', \xi_i') = \mathrm{Adh}(L(G, \xi_i))$$

puisque pour tout $L$, $\mathrm{Adh}(L) = \mathrm{Adh}(L\setminus\{\epsilon\})$ et $L^{\omega}(G', \xi_i') = L(G, \xi_i)$.

$$\text{D'où l'égalité } L^{\infty}(G', \xi_i') = L\setminus\{\epsilon\}. \quad \square$$

Revenons alors à la démonstration du théorème 4.

Soit $L$ un langage algébrique. Il existe une grammaire $G$ de Greibach réduite telle que $L(G, \xi_i) = L\setminus\{\epsilon\}$.

Il est même loisible de supposer $G$ en forme normale c'est à dire satisfaisant la condition

$$\text{pour tout } i \in [N], P_i \subset X \Xi^*.$$

Par le théorème 5, $\mathrm{Adh}(L) = \mathrm{Adh}(L\setminus\{\epsilon\}) = L^{\omega}(G, \xi_i)$ et par le théorème 3 $L(G, \xi_i) = L^{\omega}(\bar{G}, \bar{\xi}_i) [\overrightarrow{L(G)} \setminus \bar{\xi}]$ où $\bar{G}$ est la grammaire construite plus haut.

$$\text{Ainsi } \mathcal{L} = \mathrm{FG}(L^{\omega}(\bar{G}, \bar{\xi}_i) [\overrightarrow{L(G)} \setminus \bar{\xi}]).$$

Cherchons donc à quelles conditions un mot $u$ de $X^*$ est facteur gauche d'un mot de $L^{\omega}(\bar{G}, \bar{\xi}_i) [\overrightarrow{L(G)} \setminus \bar{\xi}]$. Il est clair que si $w = \alpha_1 h_1 \alpha_2 h_2 \cdots \alpha_n h_n \cdots$ est un mot de $L^{\omega}(\bar{G}, \bar{\xi}_i) [\overrightarrow{L(G)} \setminus \bar{\xi}]$, où $\bar{w} = \alpha_1 \xi_{i_1} \alpha_2 \xi_{i_2} \cdots \alpha_n \xi_{i_n} \cdots \in L^{\omega}(\bar{G}, \bar{\xi}_i)$ et pour tout $n$, $h_n \in L(G, \xi_i)$ on a $u \in \mathrm{FG}(w)$ si et seulement si il existe $k$ tel que soit $u = \alpha_1 h_1 \cdots \alpha_{k-1} h_{k-1} \alpha_k h'_k$ avec $h'_k \le h_k$.
soit $u = \alpha_1 h_1 \cdots h_{k-1} h_{k-1} \alpha'_k$ avec $\alpha'_k \le \alpha_k$.

Ceci s'écrit encore $u \in \mathrm{FG}(w) \iff$ il existe $\bar{u} \in \mathrm{FG}(\bar{w})$ tel que soit $\bar{u} \xi_{ik} \le \bar{w}$ et $u = u_i h'_k$ avec $u_i \in \bar{u} [\overrightarrow{L(G)} \setminus \bar{\xi}]$ et $h'_k \in \mathrm{FG}(L(G, \xi_i))$ soit $u \in \bar{u} [\overrightarrow{L(G)} \setminus \bar{\xi}]$.

Pour construire la grammaire $\bar{G}$ on se munit d'un alphabet

$$\mathcal{H} = \{\theta_1, \dots, \theta_N\} \text{ et l'on écrit les équations}$$

$$\begin{aligned} \bar{\xi}_i &= \bar{P}_i + \sum_j \{\alpha_j \mid \alpha_{\bar{\xi}_j} \in \bar{P}_i\} \\ &\quad + \sum_j \{\alpha_j \mid \exists \beta, \alpha_{\xi_j} \beta \in \bar{P}_i\} \\ &\quad + \sum_j \{x \in X \mid x \Xi^* \Xi \cap \bar{P}_i \neq \emptyset\} \end{aligned}$$
On a la propriété suivante :

$$L(\bar{G}, \bar{\xi}_i) = \{\bar{u}_j | \bar{u}_{\xi_j} \text{ est facteur gauche d'un mot de } L^\omega(\bar{G}, \bar{\xi}_i)\} \\ \cup \{\bar{u} | \bar{u} \in (X \cup \Xi)^* \text{ et } \bar{u} \text{ est facteur gauche d'un mot de } L^\omega(\bar{G}, \bar{\xi}_i)\}.$$

Cette propriété n'est pas difficile à démontrer du fait que $\bar{G}$ est comme $\bar{G}$ linéaire à droite et que par suite une seule règle terminale peut être utilisée dans une dérivation et ce tout à la fin.

Le langage $\mathcal{L}$ est alors égal à la substitution dans $L(\bar{G}, \bar{\xi}_i)$ de $L(G, \xi_i)$ à $\xi_i$ et $FG(L(G, \xi_i)) \setminus \{\varepsilon\}$ à $\Theta_i$ pour tout $i \in [N]$. C'est à dire que $\mathcal{L} = L(\bar{G}, \bar{\xi}_i)$ où l'on obtient $\bar{\mathcal{G}}$ en rajoutant à $\bar{\mathcal{G}}$ toutes les équations de $\mathcal{G}$ et pour chaque $\Theta_i$ les équations d'une grammaire engendrant $FG(L(G, \xi_i)) \setminus \{\varepsilon\}$ (grammaire qui peut donc être prise de Greibach).

**Exemple :**

$$G : \xi = a\xi\xi + b$$

est une grammaire qui engendre le langage de Lukasiewicz

$$\mathcal{L} = \{f \{a,b\}^* \mid |f|_a = |f|_b - 1 \text{ et } \forall f' < f : |f'|_a \ge |f'|_b\}$$

La grammaire $\bar{G}$ est la grammaire

$$\bar{G} : \bar{\xi} = a\bar{\xi} + a\xi\bar{\xi} \text{ qui engendre } L(\bar{G}, \bar{\xi}) = (a+a\xi)^\omega$$

$$\text{Ainsi } \operatorname{Adh}(\mathcal{L}) = (a+a\xi)^\omega \quad [\mathcal{L}/\xi] = (a+a\mathcal{L})^\omega \text{ et d'autre part}$$

$$\operatorname{Adh}(\mathcal{L}) = \{u \in X^\omega \mid \forall f<u, |f|_a \ge |f|_b \} \text{ par la définition de l'adhérence.}$$

Pour construire une grammaire engendrant $\mathcal{L}$ on commence par construire $\bar{\mathcal{G}}$

$$\bar{\mathcal{G}} : \bar{\xi} = a\bar{\xi} + a\xi\bar{\xi} + a\Theta + a\xi\Theta + a$$

$$\text{qui engendre } (a+a\xi)^* (a+a\Theta+a\xi\Theta).$$

Il nous faut encore une grammaire pour $FG(\mathcal{L}) \setminus \{\varepsilon\}$.

$$\text{On peut prendre } \Theta = a\xi\Theta + a\Theta + a + b + a\xi.$$

Et finalement l'on obtient $\bar{\mathcal{G}}$

$$\left\{ \begin{array}{l} \xi = a\xi\xi + b \\ \bar{\xi} = a\bar{\xi} + a\xi\bar{\xi} + a\Theta + a\xi\Theta + a \\ \Theta = a\xi\Theta + a\Theta + a + b + a \end{array} \right.$$
On vérifie que $L(G, \bar{\xi})$ n'est autre que l'ensemble des facteurs gauches propres et non vides de mots de t, comme on s'en aperçoit facilement.

## Remerciements

Nous tenons à remercier ici L. Boasson avec lequel nous avons eu d'innombrables et fructueuses discussions sur le sujet, B. Courcelle qui nous a fourni une première version du théorème 6 et attiré notre attention sur la notion d"amènité", enfin A. Arnold qui a bien voulu lire ce texte avec soin et nous a fourni d'innombrables remarques de détail qui ont permis de l'améliorer grandement.

## Bibliographie

[1] R. Cohen et A. Gold : *Theory of w-languages, I et II*
Journal Comp. and Syst. Sc. Vol 15(1977) pp- 169-208.

[2] S. Eilenberg : *Automata, languages and machines.*
Vol A, Academie Press (1974)

[3] M. Linna : On w-words and w-computations.
Annales Universitatis Furknesis, série A (1975).

[4] M. Nivat : *Mots infinis engendrés par une grammaire algébrique,*
RAIRO Inform. Theor. Vol 11 (1977) pp- 311-327.