Stabilité des langages rationnels

Le but de cet exercice est de présenter plusieurs opérations stables sur les langages rationnels. On suppose connu l’équivalence entre les langages rationnels et les langages reconnaissables par automate fini.

Exercice

Soit $\mathcal{L}_1$ et $\mathcal{L}_2$ deux langages rationnels sur l’alphabet $\Sigma$. Montrer que les langages suivants sont rationnels.

$1)$ $\overline{\mathcal{L}_1} = {\;w \in \Sigma^{*}\;|\;w \notin \mathcal{L}_1\;}$ le complémentaire de $\mathcal{L}_1$.

$2)$ $\mathcal{L}_1 \cap \mathcal{L}_2$ l’intersection de $\mathcal{L}_1$ et $\mathcal{L}_2$.

$3)$ $\mathcal{L}_1 \setminus \mathcal{L}_2$ la différence ensembliste de $\mathcal{L}_1$ et $\mathcal{L}_2$.

$4)$ $Mir(\mathcal{L}_1) = \{\;\bar{w} = w_1 w_2 \ldots w_n \in \Sigma^{*}\;|\;w_i \in \Sigma,\;w = w_n \ldots w_2 w_1 \in \mathcal{L}_1\;\}$ le langage miroir de $\mathcal{L}_1$.

$5)$ $Pre(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists v \in \Sigma^{*}, \; wv \in \mathcal{L}_1\;\}$, le langage des préfixes de $\mathcal{L}_1$.

$6)$ $Suf(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists u \in \Sigma^{*}, \; uw \in \mathcal{L}_1\;\}$, le langage des suffixes de $\mathcal{L}_1$.

$7)$ $Fac(\mathcal{L}_1) = \{\;w \in \Sigma^{*}\;|\;\exists u,v \in \Sigma^{*} \; uwv \in \mathcal{L}_1\;\}$, le langage des facteurs de $\mathcal{L}_1$.

$8)$ $\mathcal{L}_1\#\mathcal{L}_2$ : le produit mélangé de $\mathcal{L}_1$ et $\mathcal{L}_2$. Les mots mélangé sont les $u_1v_1 \ldots u_kv_k$ avec les $u_i, v_i \in \Sigma^{*}$, avec $u=u_1u_2\ldots u_k \in \mathcal{L}_1$ et $v=v_1v_2\ldots v_k \in \mathcal{L}_2$.

$9)$ $\sqrt{\mathcal{L}_1} = \{\;w \in \Sigma^{*}\;|\; ww \in \mathcal{L}_1\;\}$, la racine carré de $\mathcal{L}_1$.

$10)$ $\frac{\mathcal{L}_1}{2} = \{\;w \in \Sigma^{*}\;|\;\exists u \in \Sigma^{*},\;|w|=|u|,\; wu \in \mathcal{L}_1,\;\}$, la moitié de $\mathcal{L}_1$.

---

Correction

Dans toute la suite, on notera $\mathcal{A}_1 = \left(\Sigma,\; Q,\; q_0,\; F,\; \delta\right)$ et $\mathcal{A}_2 = \left(\Sigma,\; Q’,\; q’_0,\; F’,\; \delta’\right)$ deux automates déterministe complet reconnaissant respectivement $\mathcal{L}_1$ et $\mathcal{L}_2$.

$1)$ Un mot $w$ appartient à $\mathcal{L}_1$ si et seulement si on atteint un état de $F$ dans $\mathcal{A}_1$ lorsqu’on lit $w$. De ce fait, un mot n’est pas dans $\mathcal{L}_1$ si et seulement si on atteint un état de $Q \setminus F$ dans $\mathcal{A}_1$ lorsqu’on lit $w$. Il en résulte donc que le complémentaire de $\mathcal{L}_1$ est reconnu par l’automate : $$\overline{\mathcal{A}}_1 = \left(\Sigma,\; Q,\; q_0,\; Q \setminus F,\; \delta\right)$$ De ce fait, les langages rationnels sont stables par complémentaire.

---

$2)$ Pour deux ensembles $A$ et $B$ on rappel qu’on a la formule suivante : $$A \cap B = \overline{\overline{A} \cup \overline{B}}$$ On a donc : $$\mathcal{L}_1 \cap \mathcal{L}_2 = \overline{\overline{\mathcal{L}_1} \cup \overline{\mathcal{L}_2}}$$ Les langages rationnels étant stables par union et complémentaire, il en résulte qu’ils sont stables par intersection et $\mathcal{L}_1 \cap \mathcal{L}_2$ est rationnel.

---

$3)$ On rappel que pour deux ensembles $A$ et $B$ on a : $$A \setminus B = A \cap \overline{B}$$ On a donc que les langages rationnels sont stables par différence ensemblistes.

---

$4)$ On considère $\delta^{-1}$ la fonction qui à $(q,a) \in Q \times \Sigma$ associe l’ensemble, éventuellement vide, des états $q’$ de $Q$ tels que $\delta(q,a) = q’$. On veut montrer que $Mir(\mathcal{L}_1)$ est reconnu par l’automate non déterministe suivant : $$Mir(\mathcal{A}_1) = \left(\Sigma,\; Q,\; F,\; \{q_0\},\; \delta^{-1}\right)$$ En effet, si $w \in Mir(\mathcal{L}_1)$ alors $\bar{w} \in \mathcal{L}_1$. De ce fait, on considère la suite d’états de $q_0$ à $q’ \in F$ par lequel passe $\mathcal{A}_1$ en lisant $\bar{w}$. On note qu’un chemin dans $Mir(\mathcal{A}_1)$ en lisant $w$ est le chemin inverse de $q’$ à $q_0$. Donc on a bien $Mir(\mathcal{A}_1)$ qui reconnaît $w$. Réciproquement, si $w$ est reconnu par $Mir(\mathcal{A}_1)$ alors par définition de $\delta^{-1}$, on a un chemin de $q_0$ à un élément de $F$ dans $\mathcal{A}_1$ qui reconnait $\bar{w}$ et $w$ appartient à $Mir(\mathcal{L}_1)$. Ainsi, les langages rationnels sont stables par miroir.

---

$5)$ Soit $T$ l’ensemble des états $q$ de $\mathcal{A}_1$ tel qu’il existe un chemin de $q$ vers un état de $F$. Soit $v_q$ le mot formé par ce chemin. On considère un mot $w$ tel que $\mathcal{A}_1$ arrive dans un état $q$ de $T$ lorsqu’il le lit. On note alors que si on lit $wv_q$ on arrive dans un état de $F$. Il en résulte que $wv_q \in \mathcal{L}_1$ Donc $w \in Pre(\mathcal{L}_1)$. De plus, si $w$ est un mot préfixe de $\mathcal{L}_1$ alors il existe $v$ tel que $wv \in \mathcal{L}_1$. Donc, si $\mathcal{A}_1$ arrive dans un état $q$ en lisant $w$ alors $q \in T$. Il en résulte que $Pre(\mathcal{L}_1)$ est reconnu par l’automate suivant : $$Pre(\mathcal{A}_1) = \left(\Sigma,\; Q,\; q_0,\; T,\; \delta\right)$$ Donc le langage des préfixes d’un langage rationnel est un langage rationnel.

---

$6)$ On note que le langage des suffixes de $\mathcal{L}_1$ est le miroir du langage des préfixes de $Mir(\mathcal{L}_1)$. Il en résulte donc que le langage des suffixes d’un langage rationnel est un langage rationnel.

---

$7)$ On remarque que les facteurs d’un mot correspond à l’ensemble des préfixes de ses suffixes. On a donc : $$Fac\left(\mathcal{L}_1\right) = Pre\left(Suf\left(\mathcal{L}_1\right)\right)$$ Il en résulte que le langage des facteurs d’un langage rationnel est un langage rationnel.

---

$8)$ On pose $\Delta$ une fonction de $\left(Q \times Q’\right) \times \Sigma$ dans $\mathcal{P}\left(Q \times Q’\right)$ l’ensemble des parties de $Q \times Q’$ et définie par : $$\Delta((q,q’),a) = \left\{\;(r,q’)\;|\;\delta(q,a) = r\;\right\} \bigcup \left\{\;(q,r’)\;|\;\delta'(q’,a) = r’\;\right\}$$ On a $\mathcal{L}_1\#\mathcal{L}_2$ est reconnu par l’automate non déterministe suivant : $$\mathcal{A}_{\#} = \left(\Sigma,\;Q \times Q’,\;\{(q_0,q’_0)\},\;F \times F’,\; \Delta \right)$$ Ainsi, les langages rationnels sont stables par mélange de mots.

---

$9)$ Le principe de l’automate qu’on va construire ici est de simuler la lecture de notre mot d’entrée en partant de tous les états à la fois. Ainsi, une fois qu’on aura terminer de lire notre mot, on pourra directement le lire une seconde foi. L’ensemble d’états qui nous intéresse est donc $Q^{n}$ où $n$ est le nombre d’états de l’automate. Notre état initial est $(q_0,q_1, \ldots, q_{n-1})$ où les $q_i$ sont les états de $Q$ numérotés de $0$, l’état initial, à $n$. Notre fonction d’état $\delta_n$ est donnée par : $$\delta_n((p_0,\ldots,p_{n-1}),a) = (\delta(p_0,a), \ldots, \delta(p_{n-1},a))$$ L’ensemble des états finaux $F_{\sqrt{\;}}$ est l’ensemble des $(p_1, \ldots, p_n)$ tel que $p_1 = q_i$ et $p_{i} \in F$. Autrement dit on regarde dans quel état on se trouve après avoir lu $w$ et on en déduit où on termine après avoir lu $ww$. Ainsi l’automate $\mathcal{A}_{\sqrt{\;}}$ suivant reconnaît bien $\displaystyle \sqrt{\mathcal{L}_1}$ : $$\mathcal{A}_{\sqrt{\;}} = \left(\Sigma,\;Q^{n},\;(q_0,q_1,\ldots,q_{n-1}),\;F_{\sqrt{\;}},\;\delta_n \right)$$ Les langages rationnels sont stables par racine carrée.

---

$10)$ On procède de même que pour la racine carrée excepté qu’on utilise un automate non déterministe. Cette fois-ci, on s’intéresse à tous les états accessible à partir de chaque état. Notre automate a pour ensemble d’état $Q^{n+1}$. Notre fonction d’état $\delta_{n+1}$ est donnée par : $$\delta_{n+1}((p,p_0,\ldots,p_{n-1}),a) = \{\;(\delta(p,a),\delta(p_0,x_1), \ldots, \delta(p_{n-1},x_n)\;|\;\exists x_1,\ldots,x_n \in \Sigma\;\}$$ L’ensemble d’états finaux est l’ensemble des $(p,p_1,\ldots,p_n)$ tel que $p=p_i$ et $p_i \in F$. Enfin, l’ensemble d’états initiaux est $\{(q_0,q_0,q_1,\ldots,q_n)\}$. Ainsi, les langages rationnels sont stables par moitié.

---