IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

F

laboratoire de recherche
en informatique
et automatique

Opérateurs sur les familles
de langages

M.Nivat

Rapport de Recherche n° 106.

Mars 1975
# OPÉRATEURS SUR LES FAMILLES DE LANGAGES

M. Nivat

## Résumé :

Dans cet article nous proposons un formalisme pour dénoter un certain nombre de familles de langages que l'on construit au moyen d'une famille donnée et d'opérateurs de fermeture : fermeture par transduction rationnelle, cloture rationnelle, fermeture par substitution.

Ce qui est remarquable c'est que l'on peut établir entre ces opérateurs un certain nombre de relations d'inclusion, parfois d'identité, qui constituent autant de lennes très utiles, dont on a à se servir constamment dans la théorie des familles de langages. Nous pensons que cette façon de présenter les constructions fondamentales qui sous-tendent toute la théorie est de nature à en faciliter considérablement l'exposé et partant l'accès. Nous n'avons pourtant pas cherché à être exhaustif, de nombreux opérateurs existent dont nous ne parlons pas : nous espérons par contre donner une idée suffisante de l'économie de pensée et de moyens que peut apporter un formalisme rigoureux au traitement d'un des chapitres les plus actifs de la théorie des langages.

Nous tenons à signaler que Monsieur David J. Lewis a utilisé dans sa thèse[6] présentée à Brown University en 1971, un formalisme très voisin. Ce travail n'a malheureusement pas été publié et nous n'en avons eu connaissance qu'à un stade avancé de la rédaction du présent article.

## Abstract :

In this paper we suggest a formalism to denote several families of languages that are built from a given family and closure operators : closure by rational transduction, rational closure, closure by substitution.

Certain relations of inclusion-sometimes identity hold between these operators. They constitute very useful lemmas that are of constant
use in the theory of abstract families of languages. We think this way of introducing the fundamental constructions underlying the theory greatly facilitates its exposition and hence its accessibility. Not all operators are presented; we hope however to show sufficiently what conceptual economy can be provided by a rigourous formalism in the treatment of one of the most active branches of formal language theory.

We emphasize that D. Lewis uses in his thesis at Brown University [6] a very similar formalism. This work is unfortunately unpublished and it was brought to our attention only at a late stage in the writing of this paper.
# I. Familles de langages.

Nous désignerons par $\Omega$ un alphabet universel, dénombrable.

Tous les alphabets considérés ci-dessous sont supposés être
des sous ensembles de cet alphabet universel $\Omega$.

Nous appelerons language toute partie $L$ de $\Omega^*$, monoïde libre engendré par $\Omega$ satisfaisant la condition :

(F) Il existe un sous ensemble fini $X$ de $\Omega$ tel que $L \subset X^*$. Si $L$ satisfait la condition F il existe certainement un plus petit alphabet $X$ tel que $L \subset X^*$, nous le denoterons $X_L$ et l'appelerons alphabet de $L$.

$L$'ensemble de tous les langages sera dénoté par $\tilde{\Omega}$.

Nous appelerons famille de langages tout sous ensemble $\tilde{L}$ de $\tilde{\Omega}$ satisfaisant la condition de recopie :

(C) Pour tout $L \in \mathcal{L}$, $Y \subset \Omega$ et $\alpha$ bijection de $X_L$ sur $Y, \alpha(L)$ appartient à $L$.

Un certain nombre de familles de langages sont bien connues et nous
ne rappelerons pas leur définition.

Alg, famille des langages algébriques ou context-free

Rat, famille des langages rationnels

Nous désignerons, quand il en sera besoin, par

Fin, la famille des langages finis

Elm, la famille des monoïdes engendrés par les sous ensembles finis de $\Omega$, qui constitue bien une famille de langages.

Notre but dans cet article est plus précisément d'étudier les opérateurs sur les familles de langages. Un tel opérateur est simplement une application $\tau$ de l'ensemble $\tilde{\Omega}$ des familles de langages dans lui-même. De tels opérateurs sont bien connus et seront fort utilisé dans la suite.

- l'opérateur "morphisme" désigné par $\phi$

$$ L\phi = \{ \theta(L) \mid L \in \mathcal{L}, \theta \text{ est un morphisme de } X_L^* \text{ dans } Y^* \} $$

- l'opérateur "morphisme inverse" désigné par $\phi^{-1}$

$$ L\phi^{-1} = \{ \theta^{-1}(L) \mid L \in \mathcal{L}, \theta \text{ est un morphisme de } Y^* \text{ dans } X_L^* \} $$

- l'opérateur "intersection avec un rationnel" désigné par $I_R$

$$ L I_R = \{ L \cap K \mid L \in \mathcal{L}, K \in \text{Rat} \} $$

Ces trois opérateurs sont classiques en théorie des langages et l'on sait que chacun applique Rat dans Rat, et Alg dans Alg.
Les opérateurs, considérés comme applications, peuvent être composés. Nous noterons $\sigma\tau$ l'opérateur tel que pour tout $L \in \tilde{\Omega}$

$$L(\sigma\tau) = (L\sigma)\tau$$

L'associativité de la composition nous permet d'omettre les parenthèses. Ordonné par inclusion l'ensemble des familles de langages $\tilde{\Omega}$ est un treillis complet comme tout ensemble de parties, la condition C étant vérifiée par l'union et l'intersection d'une famille quelconque de sous ensembles de $\tilde{\Omega}$, si chacun de ces sous ensembles la vérifie. Cet ordre sur $\tilde{\Omega}$ induit un ordre sur l'ensemble des opérateurs : nous dirons que $\sigma$ est contenu dans $\tau$ et écrirons $o \subset \tau$ si et seulement si pour tout $L \in \tilde{\Omega}$, $L\sigma \subset L\tau$

Et nous dirons qu'un opérateur $\sigma$ est croissant si et seulement si pour tout $L, L' \in \tilde{\Omega}$, $L \subset L' \Rightarrow \sigma(L) \subset \sigma(L')$

C'est un résultat bien connu que l'ensemble des opérateurs croissants, muni de l'ordre induit par celui de $\tilde{\Omega}$ est encore un treillis complet. Ce qui nous permet d'affirmer que toute application continue $\Sigma$, de cet ensemble $\Theta$ d'opérateurs croissants dans lui même admet un plus petit point fixe. Autrement dit, pour toute application $\Sigma$ de $\Theta$ dans $\Theta$, plus généralement, $\Theta^n$ dans $\Theta^n$, satisfaisant :

$$\Sigma(\bigcup_{i \in I} \sigma_i) = \bigcup_{i \in I} \Sigma(\sigma_i) \text{ pour toute famille } \{\sigma_i \mid i \in I\} \text{ d'éléments de } \Theta \text{ ou } \Theta^n$$

il existe un opérateur $\bar{\sigma}$ tel que

$$1 - \Sigma(\bar{\sigma}) = \bar{\sigma}$$

$$2 - \text{Pour tout } \bar{\sigma}, \text{ tel que } \Sigma(\bar{\sigma}') = \bar{\sigma}', \bar{\sigma} \subset \bar{\sigma}'$$

De plus le même résultat classique nous permet d'affirmer que $\bar{\sigma} = \bigcup_{k \ge 0} \Sigma^k(\emptyset)$ où $\emptyset$ est l'élément minimum du treillis des opérateurs croissants tel que $L\emptyset = \emptyset$ pour tout $L$.

Tout ceci nous donne le cadre algébrique convenable pour résoudre des équations ou systèmes d'équations dont les inconnues sont des opérateurs. Ainsi, par exemple, l'équation $\tau = \tau\tau \cup \phi \cup \phi^{-1} \cup I_R$.

Nous associons à cet équation l'application $\Sigma$ de $\Theta$ dans $\Theta$ définie par $\Sigma(\tau) = \tau\tau \cup \phi \cup \phi^{-1} \cup I_R$. On vérifie aisément qu'elle est continue. Ainsi existe-t-il un plus petit opérateur, $\Gamma$, satisfaisant $\Gamma = \Gamma\Gamma \cup \phi \cup \phi^{-1} \cup I_R$. C'est l'opérateur de "transduction rationnelle" que nous étudions au § suivant. Nous dirons que $\Gamma$ est la solution de l'équation $\tau = \tau\tau \cup \phi \cup \phi^{-1} \cup I_R$.
## II. L'opérateur de transduction rationnelle Γ.

Conformément au résultat général Γ, plus petit point fixe de l'application Σ de Θ dans Θ

$$Σ(τ) = ττ \cup φ \cup φ^{-1} \cup I_R$$

est le plus petit opérateur idempotent que contienne les opérateurs de morphisme, morphisme inverse, intersection avec un rationnel.

Nous dirons l'opérateur τ idempotent si et seulement si $ττ \subset τ$.

Nous allons montrer que $Γ = φ^{-1}I_R φ$. Pour cela il suffit d'établir que $φ^{-1}I_R φ$ est idempotent. En effet l'idempotence de $φ^{-1}I_R φ$ entraine que $φ^{-1}I_R φ$ est un point fixe de Σ puisque l'opérateur "identité" Id est contenu dans chacun des opérateurs $φ^{-1}, II_R$ et $φ$. Réciproquement tout opérateur idempotent contenant $φ, φ^{-1}$ et $I_R$ contient certainement $φ^{-1}I_R φ$.

Les lesmes suivants sur lesquels nous nous appuyons sont connus mais il nous parait utile de les reformuler dans la terminologie de cet article.

**Lemme 1** $φ, φ^{-1}, I_R$ sont idempotents.

**Dem** En effet, le composé de 2 morphismes est un morphisme, et l'intersection de deux rationnels est un rationnel. □

**Lemme 2** $I_R φ^{-1} \subset φ^{-1} I_R$

**Dem** Considérons $LI_R φ^{-1} = \{ θ^{-1}(L \cap K) \mid L \in L, K \in Rat \}$ et $θ$ est un morphisme de $Y^*$ dans $X_L^*$

Nous avons $θ^{-1}(L \cap K) = θ^{-1}(L) \cap θ^{-1}(K)$ et $θ^{-1}(K) \subset Rat$.

Ainsi $θ^{-1}(L \cap K) = θ^{-1}(L) \cap K$ où $L \in L, K' \in Rat$ et $θ$ est un morphisme de $Y^*$ dans $X_L^*$, et par suite $θ^{-1}(L \cap K) \subset L φ^{-1} I_R$. Comme ceci est vrai pour tout $L, K$ et $θ$ on a bien $L I_R φ^{-1} \subset L φ^{-1} I_R$. Et comme ceci est vrai pour tout $L$, on a l'inclusion cherchée $I_R φ^{-1} \subset φ^{-1} I_R$. □

**Lemme 3** $φ I_R \subset I_R φ$

**Dem** Considérons $θ(L) \cap K \subset L φ I_R$. Nous avons $θ(L) \cap K = θ(L \cap θ^{-1}(K)) = θ(L \cap K')$ où $K' = θ^{-1}(K) \in Rat$. On en conclut comme précédemment $θ(L) \cap K \subset L I_R φ$ pour tout $L \in L, K \in Rat$, $θ$ morphisme de $X_L^*$ dans $Y^*$ d'où $L φ I_R \subset L I_R φ$ pour tout $L \in \tilde{\Omega}$ d'où l'inclusion cherchée. □
Avant d'aller plus loin introduisons les opérateurs $\phi_a$ et $\phi_a^{-1}$ de "morphisme alphabétique" et de "morphisme alphabétique inverse".

Nous disons que le morphisme $\theta$ de $X^*$ dans $Y^*$ est alphabétique si et seulement si $\theta(X) \subset Y \cup \{1\}$.

Par définition pour tout $L \in \tilde{\Omega}$ :

$$L \phi_a = \{ \theta(L) \mid L \in L \text{ et } \theta \text{ est un morphisme alphabétique de } X_L^* \text{ dans } Y^* \}$$

$$L \phi_a^{-1} = \{ \theta^{-1}(L) \mid L \in L \text{ et } \theta \text{ est un morphisme alphabétique de } Y^* \text{ dans } X_L^* \}$$

Lemme 4 : $\phi_a \phi_a^{-1} \subset \phi_a^{-1} \phi_a$

Dem
Il suffit de montrer que si $\theta$ est un morphisme alphabétique de $X^*$ dans $Z^*$ et $\theta'$ un morphisme alphabétique de $Y^*$ dans $Z^*$ il existe un alphabet U, deux morphismes alphabétiques $\chi$ et $\chi'$ de $U^*$ dans $X^*$ et $Y^*$ respectivement tels que pour tout $f \in X^* \theta'^{-1}(\theta(f)) = \chi' \chi^{-1}(f)$.

La construction est répétée de [7]

On prend :

$$U = \{ (x,\omega) \mid x \in X \mid \theta(x) = 1 \} \cup \{ (\omega,y) \mid y \in Y, \theta'(y) = 1 \}$$

$$\cup \{ (x,y) \mid x \in X, y \in Y, \theta(x) = \theta'(y) \}$$

Le symbole $\omega$ désigne une lettre qui n'appartient pas à $X \cup Y$.
( U tel quel n'est pas une partie de $\Omega$ mais il est facile de le mettre en
correspondance biunivoque avec une telle partie ).

$$\chi(\omega,y) = 1 \quad \chi(x,\omega) = \chi(x,y) = x$$

$$\chi'(\omega,y) = \chi'(x,y) = y \quad \chi'(x,\omega) = 1.$$

La vérification est immédiate. $\square$

Lemme 5 : $\phi \subset \phi_a^{-1} I_R \phi_a$ et $\phi^{-1} \subset \phi_a^{-1} I_R \phi_a$

Dem
La construction se trouve aussi dans [7]

Soit $\theta : X^* \to Y^*$

$$\text{On prend l'alphabet } Z = \{ (x,n) \mid x \in X, 0 \le n \le \theta(n) \mid \}$$

$\chi$ est le morphisme de $Z^*$ dans $X^*$ donné par $\chi(x,0) = x$ et $\chi(x,n) = 1$ pour tout $n \ge 1$.

$\chi'$ est le morphisme de $Z^*$ dans $Y^*$ donné par $\chi(x,0) = 1$ et $\chi'(x,n) = n$ pour tout $n \ge 1$.
lettre de $\theta(x)$.

Enfin $K \in \text{Rat}$ est le rationnel défini par

$$K = AZ^* \cap Z^* B \setminus Z^* V Z^* \text{ où}$$

$$A = \{ (x,0) \mid x \in X \} \quad B = \{ (x, \theta(n)) \mid x \in X \}$$

$$\text{et } Z^2 \setminus V = \{ (x,n) (x,n+1) \mid x \in X \text{ et } n < \theta(x) \} \cup BA.$$
On vérifie aisément que pour tout $f \in X^*$

$\Theta(f) = \chi' ( \chi^{-1}(f) \cap K )$ et que pour tout $g \in Y^*$

$\Theta^{-1}(g) = \chi ( \chi^{-1}(g) \cap K )$.

Les deux inclusions cherchées sont ainsi démontrées simultanément. $\square$

**Théorème :** $\phi^{-1} I_R \phi$ est idempotent et par suite $\Gamma = \phi^{-1} I_R \phi$.

$$
\begin{align*}
\text{Dem} \qquad & \phi^{-1} I_R \phi \phi^{-1} I_R \phi \subset \phi^{-1} I_R \phi_a^{-1} I_R \phi_a \phi_a^{-1} I_R \phi_a I_R \phi \\
\qquad & \subset \phi^{-1} I_R \phi_a^{-1} I_R \phi_a^{-1} \phi_a I_R \phi_a I_R \phi \\
\qquad & \subset \phi^{-1} \phi_a^{-1} \phi_a^{-1} I_R I_R I_R I_R \phi_a \phi_a \phi \subset \phi^{-1} I_R \phi. \quad \square
\end{align*}
$$

**Remarques 1.** Il est facile de démontrer que $\Gamma = \phi_a^{-1} I_R \phi_a$

2. Tout élément $L \Gamma$ s'écrit puisque $\Gamma = \phi^{-1} I_R \phi$
$L' = \Theta'( \Theta^{-1}(L) \cap K ) \text{ où } L \in L, \Theta \text{ est un morphisme de}
Z^* \text{ dans } X_L^*, \Theta' \text{ un morphisme de } Z^* \text{ dans } X_L^*, \text{ et } K \in \text{Rat.}
C'est à dire, s'écrit $L' = \gamma(L)$ où $\gamma$ est l'application définie
par $\gamma(f) = \Theta'( \Theta^{-1}(f) \cap K )$ pour tout $f \in X_L^*$.
On reconnait en $\gamma$ une transduction rationnelle dans la termino-
logie de $[]$, une application définie par un "a-transducer" dans
la terminologie de $[]$.
### III. Cônes rationnels.

Toute famille de langage fermée par morphisme, morphisme inverse et intersection avec un rationnel est appelée cône rationnel.

Si $L$ est une famille de langages, puisque $\tilde{\Omega}$ est un treillis, il existe un plus petit cône rationnel contenant $L$ que nous noterons $C(L)$ et appelerons le cône rationnel engendré par $L$.

A priori $C(L) = \bigcup L\sigma$ où $\sigma$ parcourt l'ensemble des produits quelconques des opérateurs $\phi, \phi^{-1}$ et $I_R$ ce que nous notons $\sigma \in (\phi \cup \phi^{-1} \cup I_R)^*$. Mais $\bigcup \{ \sigma \mid \sigma \in (\phi \cup \phi^{-1} \cup I_R)^* \}$ n'est autre que le plus petit point fixe de $\Sigma$ définie par $\Sigma(\tau) = \tau \tau \cup \phi \cup \phi^{-1} \cup I_R$ puisque c'est $\bigcup_{k \ge 0} \Sigma^k (\emptyset)$.

On a donc $C(L) = L\Gamma$.

On remarquera ici que $(\phi \cup \phi^{-1} \cup I_R)^* \subset \Gamma$ se démontre directement à partir des lemmes 1 à 4.

Nous pouvons énoncer

**Théorème** : Le cône rationnel engendré par une famille de langages $L$ est égal à l'ensemble des images par transductions rationnelles des éléments de $L$.

Un concept interviendra dans la suite, celui de cône principal :

Un cône rationnel $L$ est dit principal si et seulement si il existe un langage $L$ tel que $L$ soit engendré par la famille formée de $L$ et de toutes ses copies ( image de $L$ dans une bijection quelconque ). Nous notons alors $L = C(L)$.
#### IV. Opérateurs de substitution.

Si $L$ est une famille de langages, nous appellerons $L$-substitution de $X^*$ tout morphisme $\sigma$ de $X^*$ dans l'ensemble des parties de $\Omega^*$ tel que pour tout $x \in \Lambda$ $\sigma(x) \in L$.

L'opérateur de $L$-substitution, noté $\overline{L}$, est défini par

$$ \text{- Par toute } M \in \hat{\Omega} \qquad \overline{ML} = \{ \sigma(M) \mid M \in M \text{ et } \sigma \text{ est une } L\text{-substitutib de } X_M^* \} $$

On a les propriétés suivantes :

**Propriété 1** - $\overline{L}$ est un opérateur croissant ( de façon évidente )

**Propriété 2** - $L_1 \subsetneq L_2 \implies \overline{L_1} \subsetneq \overline{L_2}$ ( de façon non moins évidente )

**Propriété 3** - $\overline{L_1} \overline{L_2} = \overline{L_1 L_2}$

**Dem** On peut compose les substitutions et clairement si $\sigma_1$ est une $L_1$-substitution, $\sigma_2$ est une $\sigma_2$-substitution la substitution $\sigma_1 \circ \sigma_2$ est une $L_1 \overline{L_2}$-substitution puisque $\sigma_1 \circ \sigma_2(x) = \sigma_2(\sigma_1(x))$ appartient à $L_1 \overline{L_2}$ pour tout $x \in X$. **Réciproquement.** Soit $\sigma$ une $L_1 \overline{L_2}$ substitution. Pour tout $x \in X$ on peut écrire $\sigma(x) = \sigma_{2,x}(L_x)$ où $L_x \in L_1$ et $\sigma_{2,x}$ est une $L_2$-substitution. Grace à la condition de recopie (C) on peut trouver des langages $L'_x$ sur des alphabets disjoints tels que pour tout $x$

$$ L'_x = \alpha_x(L_x) \in L_1, \text{ où } L_x \text{ est une bijection de } X_{L_x} \text{ sur } X_{L'_x} \\ \text{( on dit alors que } L'_x \text{ est une copie de } L_x \text{)} $$

On peut alors définir la $L_1$-substitution $\sigma_1$ de $X^*$ par $\sigma_1(x) = L'_x$ pour tout $x$ et la $L_2$-substitution $\sigma_2$ de $Y^*$ où $Y = \bigcup_{x \in X} L_x$, par $\sigma_2(y) = \sigma_{2,x}(\alpha_x^{-1}(y))$. Il est immédiat que $\sigma = \sigma_1 \circ \sigma_2$. $\square$

Nous utiliserons aussi l'opération de cloture par $L$, noté $\underline{L}$ et lié aux opérateurs de substitution par

$$ \text{Pour tout } L, M \in \hat{\Omega} \qquad ML = \overline{LM} $$

Cette identité nous permet de transformer tout énoncé concernant les opérations de substitution en énoncé sur les opérateurs de cloture et vice-versa.

C'est ainsi que l'on a les

**Propriété 1'** $L_1 \subsetneq L_2 \qquad L_1 \subsetneq L_2$ (équivalente à la propriété 1)

**Propriété 2'** $\underline{L}$ est un opérateur croissant (équivalente à la propriété 2)

**Propriété 3'** $\overline{L_1 L_2} = \overline{L_1 L_2}$

**Dem** En effet pour tout $M, L_1, L_2$ nous avons

$$ M \overline{L_1 L_2} = \overline{L_1 M} \overline{L_2} = \overline{L_2 L_1 M} = \overline{L_2 \overline{L_1 M}} = \overline{L_1 \overline{L_2 M}} = M \overline{L_1 L_2} \quad \square $$
Parni ces opérateurs de cloture l'un est bien connu c'est la cloture rationnelle qui dans notre formalisme s'écrit $\underline{\underline{Rat}}$: pour tout $L$, $\underline{\underline{L Rat}}$ est en effet l'ensemble des images d'un rationnel quelconque dans une $L$-substitution, c'est à dire aussi en remontant à la définition de $\underline{\underline{Rat}}$, la plus petite famille de langages contenant $L$ et fermée, union, produit et étoile. De la même façon $\underline{\underline{Fin}}$ est la cloture polynomiale ( par union et produit ) et $\underline{\underline{Elm}}$ la cloture par union et étoile. Alg peut, à bon droit, s'appeler la cloture algébrique.

Il est bien connu que $\underline{\underline{Rat}} = \underline{\underline{Rat}}$ et $\underline{\underline{Alg}} = \underline{\underline{Alg}}$. $\underline{\underline{Rat}} = \underline{\underline{Rat}}$ est équivalent à $\underline{\underline{Rat}} = \underline{\underline{Rat}}$ qui nous servira aussi dans la suite.

**Proposition 4.** $\underline{\Gamma} \subset \Gamma \underline{\Gamma}$ et de façon équivalente $\bar{M} \Gamma \subset \Gamma \bar{M}\Gamma$

Nous utilisons la remarque 1 suivant le théorème 1, à savoir $\Gamma = \phi_a^{-1} I_R \phi_a$. Dem De façon évidente $\underline{\Gamma} \phi_a^{-1} \subset \phi_a^{-1} \underline{\Gamma}$ et $\underline{\Gamma} \phi_a \subset \phi_a \underline{\Gamma}$

Considérons maintenant $\sigma(L) \cap K$ où $L \in \underline{\underline{L}}, K \in \underline{\underline{Rat}}$ et $\sigma$ est une $M$-substitution de $X_L^*$. Supposons K reconnu par l'automate fini $A = \langle S, s_0, S', \lambda \rangle$ et définissons pour tout $s,s' \in$ le langage $K_{s,s'} = \{ f \mid \lambda(s,f) = s' \}$. $K_{s,s'}$ est pour tout $s,s'$ un langage rationnel.

L'application $\tau$ qui applique le mot $x_1...x_p \in X_L^*$ sur l'ensemble des mots $(s_0,x_1,s_1)(s_1,x_2,s_2)...(s_{p-1},x_p,s_p)$ où pour tout $i=0,...,p$ $s_i \in S$ et $s_p \in S$ est une transduction rationnelle. D'où $\tau(L) \in \underline{\underline{L\Gamma}}$

Si la définit la substitution $\sigma'$ de $(SxxS)^*$ par $\sigma'(s,x,s') = K_{s,s'} \cap \sigma(x)$ pour tout $s,s' \in S$, $x \in X$, $\sigma'$ est une $M\Gamma$-substitution. Et par ailleurs on a l'égalité aisément vérifiée $K \cap \sigma(L) = \sigma'(\tau(L))$.

On en déduit $\underline{\underline{I_R}} \subset \underline{\underline{I_R}} \underline{\underline{L\Gamma}}$.

Finalement $\underline{\underline{\phi_a^{-1} I_R \phi_a}} \subset \underline{\underline{\phi_a^{-1} I_R \underline{\underline{\Gamma}} \phi_a}} \subset \underline{\underline{\phi_a^{-1} I_R \underline{\underline{\Gamma}} \phi_a}} \subset \underline{\underline{\phi_a^{-1} I_R \phi_a \underline{\underline{\Gamma}}}} = \underline{\underline{\Gamma \underline{\underline{\Gamma}}}}$ $\square$
## V. L'opérateur de FAL engendré.

Nous appelerons famille agréable de langages toute famille fermée par morphisme, morphisme inverse, intersection avec un rationnel et les opérations rationnelles d'union produit et étoile. Nous abrigeons famille agréable de langages en FAL. Ce concept a été introduit dans [ 3] sous le nom de "full AFL" où AFL est une abréviation de "Abstract family of languages".

Dans nos notations $L$ est une FAL si et seulement si

$$L \Gamma \subset L \text{ et } L \underline{\Gamma} \subset \underline{L}$$

L'ensemble des familles de langages $\hat{\Omega}$ étant un treillis, il existe une plus petite FAL contenant une famille de langages $L$ donné, que nous noterons $F(L)$ et appelerons la FAL engendrée par $L$.

$$A \text{ priori } F(L) = \underline{L} \{ L \mid \sigma \in ( \Gamma \cup \underline{\Gamma} )^* \}$$

Mais d'après la propriété 4

$$\underline{\Gamma} \Gamma \subset \Gamma \underline{\Gamma} \text{ et comme } \underline{\Gamma} \Gamma = \Gamma \underline{\Gamma}$$

$$\underline{\Gamma} \Gamma \subset \Gamma \underline{\Gamma} \text{ et comme } \underline{\Gamma} \Gamma = \Gamma \underline{\Gamma}$$

Comme de plus $\Gamma \subset \Gamma$ et $\underline{\Gamma} \subset \underline{\Gamma}$ on a pour tout $\sigma \in ( \Gamma \cup \underline{\Gamma} )^*$ $\sigma \in \Gamma \underline{\Gamma}$ et par suite $F(L) = \Gamma \underline{\Gamma}$ ce qui est un théorème de [ 3].

Nous appelerons $\Gamma \underline{\Gamma}$ l'opérateur de FAL engendré. Nous pouvons énoncer Théorème : La fermeture rationnelle d'un cône rationnel est une FAL.

Pour toute famille de langages $L$, la FAL engendrée par $L$ est la fermeture rationnelle du cône rationnel engendré par $L$.

Comme dans le cas des cônes, nous dirons qu'une FAL $L$ est principale si et seulement si il existe un langage $L$ tel que $L = F(L)$.

La propriété 4 a d'autres corollaires

**Théorème [ 4]** Si $L$ et $M$ sont des cônes rationnels ( resp des FAL ) $LM$ est un cône rationnel ( resp une FAL )

**Dem** On a $L \Gamma \subset L$ et $M \Gamma \subset M$ si $L$ et $M$ sont des cônes.

$$\text{D'où } LM \subset L \Gamma \subset M \text{ et } LM \text{ est un cône.}$$

Si de plus $L$ et $M$ sont rationnellement fermé on a $L \underline{\Gamma} \subset L$ et $M \underline{\Gamma} \subset M$ d'où $LM \underline{\Gamma} \subset LM \text{ et } LM \text{ est une FAL.}$
## Familles de langages marquées

Un langage marqué est un langage dont tous les mots se terminent par un marqueur de fin de mot, lettre qui n'a qu'une occurrence dans le mot, à la fin.

Ainsi un langage $L$ est marqué si et seulement si

$$L = L'\{c\} \text{ où } c \in \Omega\X_L,$$

Nous écrirons $L = L'$c'écriture qui ne prête pas à confusion.

Nous définirons l'opérateur de marquage, traditionnellement désigné par $\#\text{en posant pour toute famille de langages } L$

$$L^\# = \{ Lc \mid L \subset L \text{ c } \in \Omega\X_L \}$$

**Proposition 5.** $\overline{L\Gamma} \in L^\#\Gamma$ et de façon équivalente $\Gamma M \subset \#\Gamma$

**Démonstration :** Soit $\sigma$ une $L\Gamma$-substitution de $X_M^*$. On a pour tout $x \in X_M$ $\sigma(x) = \tau_X(L_X)$ où $L_X \in L$ et $\tau_X$ est une transduction rationnelle. On peut supposer, sans perte de généralité, que $L_X \subset (\Omega\X_M)^*$ en sorte que la substitution définie par $\sigma'(x) = L_X$ soit une $L^\#$-substitution. Construisons une transduction rationnelle $\tau$ tel le que pour tout $f \in X_M^* \cup \{\sigma'(f)\} = \sigma(f)$.
Pour cela on écrit pour tout $x$

$\tau_X(g) = \chi_X(\Theta_X^{-1}(g) \cap K_X)$ où $K_X \subset Z_X$ et $\Theta_X, \chi_X$ sont des morphismes alphabétiques de $Z_X^*$ dans $X_{L_X}^*$ et $X_{\sigma(X)}^*$ respectivement.

On peut certainement supposer les alphabets $Z_X$ disjoints entre eux et disjoints de $X_M$.

On définit alors les trois alphabets :

$$U = \bigcup \{ Z_X \mid x \in X \} \cup X_M$$

$$V = \bigcup \{ X_{L_X} \mid x \in X \} \cup X_M$$

$$W = \bigcup \{ X_{\sigma(x)} \mid x \in X \}$$

les deux morphismes alphabétiques $\Theta$ et $\chi$ de $U^*$ dans $V^*$ et $W^*$

$$\Theta(z) = \Theta_X(z) \text{ par } z \in Z_X \quad \Theta(x) = x \text{ par } x \in X_M$$

$$\chi(z) = \chi_X(z) \text{ par } z \in Z_X \quad \chi(x) = 1 \text{ par } x \in X_M$$

et le rationnel $K = ( \bigcup \{ K_X x \mid x \in X_M \} )^*$

La transduction $\tau$ cherchée est définie par $\tau(f) = x(\Theta^{-1}(f) \cap K)$ □
**Proposition 6** $\Gamma \overline{M} \subset \overline{Elm} \ \overline{M}^# \ \Gamma$ et de façon equivalente
$L\Gamma \subset \underline{Elm} \ \underline{M}^# \ \Gamma$

**Démonstration**

Nous avons besoin de plusieurs petits lemmes

1. $\phi_a \bar{M} \subset \bar{M} \phi_a$ évident

2. $I_R \bar{M} \subset \bar{M}^# I_R$

Considérons une M-substitution $\sigma$ de $L \cap K \in LI_R$.

On peut supposer pour tout $x \in X_L$ $\sigma(x) \in (\Omega \setminus X_L)^*$ et par suite
définir la M#-substitution $\sigma'$ par

$$ \sigma'(x) = \sigma(x) \quad \text{pour tout} \quad x \in X_L $$

Définissons la Rat-substitution $\sigma''$ donnée par

$$ \sigma''(x) = X_{\sigma(x)}^{*} x $$

et le morphisme alphabétique $\chi$ donné par

$$ \chi(z) = z \text{ pour tout } z \in \chi_{\sigma(x)} \quad \chi(x) = 1 \text{ pour tout } x \in X_L $$

On vérifie aisément que

$$ \sigma(L \cap K) = \chi(\sigma'(L) \cap \sigma''(K)) $$

3. $I_R \bar{M}^# \subset \bar{M}^# I_R$

La construction est la même que précédemment.

Ecrivons pour tout $x \in M_X \bar{x} \subset M^#$

et munissons nous d'un alphabet Z en correspondance biunivoque
avec $X_L$. On note $z_X$ la lettre de Z correspondant à x.

On définit $\sigma'(x) = M_X z_X$

$$ \sigma'' = X_{M_X}^* \quad \text{enfin} \quad (z) = z \text{ pour tout } z \in X_{M_X} \text{ et } \chi(z_X) = \bar{x} \\ \text{pour tout } x \in X_L. $$

On a toujours $\sigma(L \cap K) = \chi(\sigma'(L) \cap \sigma''(K))$

4. $\overline{M}^# I_R \subset \overline{M}^# I_R$

Soit en effet $\sigma$ une $M^# I_R$ substitution de L

$$ \sigma(x) = M_X \bar{x} \cap K_X \quad \text{pour tout} \quad x \in X_L. $$

On a si l'on définit la substitution $\sigma'(x) = M_X \bar{x}$
et le rationnel $( \cup \{ K_X \cap X_{M_X}^* \bar{x} \mid x \in X \} )^* = K'$
$\sigma(L) = \sigma'(L) \cap K'$
$$5 - \phi_a^{-1} \subset \overline{\mathrm{Rat}} \subset \overline{\mathrm{Elm}} I_R$$

En effet soit $\theta$ un morphisme alphabétique de $Y^*$ dans $X^*$

$\theta^{-1}$ n'est autre que la Rat-substitution donnée par

$$\theta^{-1}(x) = Y_o^* Y_x Y_o^* \text{ où}$$

$$Y_o = \{ y \in Y \mid \theta(y) = 1 \} \text{ et pour tout } x \in X$$

$$Y_x = \{ y \in Y \mid \theta(y) = x \}$$

Rat $\subset \overline{\mathrm{Elm}} I_R$ est évident

Finalement on a :

$$\Gamma \bar{M} \subset \phi_a^{-1} I_R \phi_a \bar{M} \subset \phi_a^{-1} I_R \bar{M} \phi_a \\ \subset \phi_a^{-1} \bar{M} \# I_R \phi_a \subset \overline{\mathrm{Elm}} I_R \bar{M} \# I_R \phi_a$$

$$\overline{\mathrm{Elm}} I_R \bar{M} \# \subset \overline{\mathrm{Elm}} \bar{M} \# I_R$$

$$\overline{\mathrm{Elm}} I_R \bar{M} \# = \overline{\mathrm{Elm}} I_R \bar{M} \# \subset \overline{\mathrm{Elm}} \bar{M} \# I_R$$

$$\subset \overline{\mathrm{Elm}} \bar{M} \# I_R \subset \overline{\mathrm{Elm}} \bar{M} \# I_R$$

D'où le résultat $\square$

**Corollaire 1** - $\Gamma \overline{\mathrm{M}} \subset L \overline{\mathrm{Elm}} \overline{\mathrm{M}} \# \Gamma$

Cet énoncé nous décrit un système générateur du cône rationnel $\Gamma \overline{\mathrm{M}}$ connaissant des systèmes générateurs $L$ et $M$ des cônes rationnels $\Gamma$ et $M$.

Si ces deux derniers cônes rationnels sont principaux $L = \{L\}$ et $M = \{M\}$ un système générateur de $\Gamma \overline{\mathrm{M}}$ est la famille $L \overline{\mathrm{Elm}} \overline{\mathrm{M}} \#$

De là on peut extraire un générateur unique.

Tout langage de $L \overline{\mathrm{Elm}} \overline{\mathrm{M}} \#$ s'écrit en effet $\sigma(L)$ où $\sigma$ est une substitution définie par

$$\text{pour tout } x \in X \quad \sigma(x) = \left( \bigcup_{i=1}^{u} \alpha_{i,x} (M_x) \right)^*$$

en désignant par $\alpha_{i,x}$ une bijection quelconque de $\{x\} \cup X_M$ et en supposant $M \subset (\Omega \setminus X_L)^*$ ce qui est loisible.

Définissons la substitution $\pi$ par $\pi(x) = (M_x)^*$ et la transduction rationnelle $\tau$ suivante.

Pour tout $i,x$ prenons un alphabet $Z_{i,x}$ en correspondance biunivoque avec $\{x\} \cup X_M$ de façon que ces alphabets soient disjoints. On écrira $Z_{i,x} = \beta_{i,x} (\{x\} \cup X_M)$. Soit $\theta$ le morphisme de $Z^* = (\cup Z_{i,x})^*$ sur $(X_L \cup X_M)^*$ défini par $\theta(z) = \beta_{i,x}^*(z)$ pour tout $z \in Z_{i,x}$ et $\chi$ le morphisme de $Z^*$ sur $(\cup \alpha_{i,x} (\{x\} \cup X_M))$ défini par $\chi(z) = \alpha_{i,x} (\theta(z))$ pour tout $z \in Z_{i,x}$.
Soit enfin $K = ( \cup (Z_{i,x} \setminus \beta_{i,x}^{-1}(x))^* \beta_{i,x}^{-1}(x))^*$

On a $\sigma(L) = \tau(\pi(L))$

Et l'on a établi un résultat de [4]

**Théorème** - Si $C(L)$ et $C(M)$ sont deux cônes principaux $C(L)$ $C(M)$ est un cône principal ayant pour générateur $\sigma(L)$ où $\sigma(x) = (M_x)^*$ pour tout $x \in X_L$.

Nous avons un résultat tout à fait semblable concernant les systèmes générateurs des FAL. En effet

**Corollaire 2.** Let $\Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \subset L \mathfrak{E} \mathfrak{m} \mathfrak{M} \# \Gamma \mathfrak{R} \mathfrak{A}$

En effet $L \Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \subset L \Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \subset L \Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A}$ mais $L \Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \subset L \Gamma \mathfrak{R} \mathfrak{A}$ puisque $L \Gamma \mathfrak{R} \mathfrak{A}$ est un cône rationnel fermé par substitution rationnelle.

$D'$où $L \Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \subset L \Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A}$

$\Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \subset \Gamma \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A} \mathfrak{R} \mathfrak{A}$

Par le même argument que précédemment on établit alors l'autre résultat [4]

**Théorème.** Si $F(L)$ et $F(M)$ sont deux FAL principales $F(I)$ $F(M)$ est une FAL principale ayant pour générateur $\sigma(L)$ où $\sigma(x) = (M_x)^*$ pour tout $x \in X_L$.

**Clôture par substitution**

La famille de langages $L$ est dite fermée par $M$-substitution si et seulement si pour tout langage $L \in L$ et $M$-substitution $\sigma$

$\sigma(L) \in L$

ce qui s'écrit dans notre formalisme $L \bar{M} \subset L$

L'opérateur $\bar{M}^*$ tel que $L \bar{M}^*$ soit la plus petite famille de langages contenant $L$ et fermée par $M$-substitution s'obtient comme solution de l'équation.

$\tau = \tau \tau \cup \bar{M}$

et par suite égal à $\bar{M}^* = \bigcup_{k \ge 1} \bar{M}^k$

$\bar{M}^*$ est appelé opérateur de clôture par $M$-substitution.

**Proposition 1** $M \bar{M} \subset M \Rightarrow \bar{M}^* = \bar{M}$

S'obtient immédiatement à partir de III.3.

$\bar{M}^2 = \bar{M} \bar{M} = \bar{M} \subset \bar{M}$ et par induction $\bar{M}^k \subset \bar{M}$ pour tout $k$.
**Proposition 2** $\overline{M^*} \Gamma \subset \Gamma(\overline{M\Gamma})^*$

S'obtient à partir de III.4. $\overline{M\Gamma} \subset \Gamma \overline{M\Gamma}$ et par induction $\overline{M}^k \Gamma \subset \Gamma(\overline{M\Gamma})^k$ pour tout k

**Corollaire 1** Si $L$ et $M$ sont des cônes rationnels $L\overline{M}^*$ est un cône rationnel.

En effet $M\Gamma \subset M$ implique $\overline{M}^*\Gamma \subset \Gamma\overline{M}^*$ d'où $L\overline{M}^*\Gamma \subset L\Gamma\overline{M}^* \subset L\overline{M}^*$

**Corollaire 2** Si $L$ est une FAL et $M$ un cône rationnel $L\overline{M}^*$ est une FAL.

En effet $L\overline{M}^*$ **Rat** = **Pat** $L\overline{M}^* = \text{Rat } L M^* \subset L\overline{M}^*$ puisque $L \text{ **Rat**} = \text{Rat } \overline{L} \subset L$, $\overline{L}$ étant une FAL.

Tous ces résultats figurent dans [4].

Toute famille de langages $\mathcal{L}$ fermée par $\mathcal{L}$-substitution est dite fermée par substitution. Ainsi la famille $\mathcal{L}$ est fermée par substitution si et seulement si $\overline{\mathcal{L}} \subset \mathcal{L}$.

Il est clair que la plus petite famille de langages fermée par $\mathcal{L}$-substitution contenant $\mathcal{L}$ est la famille $\overline{\mathcal{L}}^*$.

De remarquables propriétés de cette clôture ont été établies par S. Greibach [5]. Nous les rappelons ci-dessous.

**Théorème** : Si $L$ et $M$ sont des cônes rationnels fermés par union, $L\overline{M}$ est fermé par substitution, seulement si $L\overline{M} \subset L \cup M$.

La démonstration repose sur le lemme suivant :

Définissons la substitution marquée de $I_2$ dans $L_1$, où $L_1$ et $I_2$ sont des langages portés par des alphabets comme

$$L_1 \text{ s} I_2 = \{ x_1 u_1 x_2 u_2 \dots x_k u_k \mid j = 1, \dots, k \ x_j \in X_{L_1}, u_j \in L_2 \text{ et } x_1 \dots x_k \in L_1 \}$$

**Lemme** : Si $L_1$ et $L_2$ sont des cônes rationnels fermés par union $L_1 s L_2 \in L_1 \overline{L_2}$ implique $L_1 \in L_1$ ou $L_2 \in L_2$.

La démonstration du théorème est alors immédiate :
Prenons $L \in \overline{L}$ et une copie $L'$ de $L$ sur un alphabet $X_L$, disjoint de $X_L$.
Certainement $L \subset L'$ et $L \subset \overline{L}$ d'où puisque $L\overline{M}(L\overline{M}) \subset L\overline{M}$, $L\overline{S}(L') \in L\overline{M}$. Ce qui implique $L \subset L$ ou $L' \in M$ soit $L \in L \cup M$.

**Corollaire** : Si $L$ est un cône rationnel fermé par union, $L \text{ **Rat**}$ est fermé par substitution si et seulement si $L$ est fermé par substitution. En ce cas $L = L \text{ **Rat**}$ est une FAL.
En effet, en vertu du théorème, $L \underline{\text{Rat}} \subset L \cup \text{Rat}$. Mais Rat est contenu dans $L$ d'où $L \underline{\text{Rat}} \subset L$.

**Corollaire** : Si $L$ est un cône rationnel fermé par union, mais non pas par substitution, la suite des cônes $LL^k$ est strictement croissante et par suite la fermeture par substitution de $L$, $LL^* = \bigcup_{k \ge 0} LL^k$ est un cône non principal.

Supposons qu'il existe un entier $k$ tel que $LL^k = LL^{k+1}$ et choisissons le plus petit. On a certainement $LL^{k+1} = LL^k$ pour tout $\ell$ et il existe un langage $L \in LL^k \setminus LL^{k-1}$. Si $L'$ est une copie de $L$ sur un alphabet disjoint $L \llcorner L'$, $L \llcorner LL^k = L \llcorner LL^{k+1} = L \llcorner LL^k$

De $L \llcorner L'$, $L \llcorner LL^k$ on tire

$L \in LL^{k-1} \cup L = LL^{k+1}$ ce qui n'est pas.

La non principalité de $LL^*$ en découle car si l'on avait $LL^* = \{L\}$, pour quelque $L$ on aurait $L \in \bigcup_{k \ge 0} LL^k$ d'où $L \in LL^k$ pour quelque $k$, $LL^k$ serait ainsi égal à $LL^*$ donc fermé par substitution et la suite des $LL^k$ ne serait pas strictement croissante.

Dans [1] et [2] nous avons utilisé des techniques tout à fait similaire pour démontrer la non principalité de diverses clotures de famille de langages par des ensembles d'opérateurs contenant le crochet :

On définit pour tout langage $L \in X_L^*$ et partie rationnelle $A$ de $Y^* \times Z^*$ le crochet $[L,A] = \{ f \mid g^R \mid (f,g) \in A, f \in L \}$ et si $L$ est une famille de langages le crochet de $L$ connue

$$L[\cdot] = \{ [L,A] \mid L \in L, A \in \text{Rat}(Y^* \times Z^*) \}$$

Des problèmes non encore résolus se posent en ce qui concerne le plus petit cône principal fermé par substitution, dont une conjecture veut qu'il soit précisement égal à Alg. Les techniques évoquées ci-dessus ne sont pas suffisantes pour le démontrer.
[1] L. Boasson, M. Nivat : Sur diverses familles de langages fermées par transduction rationnelle, Acta Informatica 2 (1973) 180-188.

[2] L. Boasson, JP. Grestin, M. Nivat : Familles de langages translatables et fermées par crochet, Acta Informatica 2 (1973) 383-393.

[3] S. Ginsburg, S. Greibach, J. Hopcroft : Studies in Abstract Families of Languages, Memoirs Amer. Math Soc n° 87, Providence, 1969.

[4] S. Ginsburg, E. Spanier : Substitution in Families of Languages, Information Sciences 2 (1970) 83-110.

[5] S. Greibach : Chains of full AFL's, Math System Theory 4 (1970) 231-242.

[6] David J. Lewis : Closure of Classes of Formal Languages under substitution operators, Ph D thesis, Brown University, 1971.