An algebraic language whose complement is not algebraic (the language of non-squares).

1 files changed, 114 insertions, 13 deletions

diff --git a/exercices2.tex b/exercices2.tex
index e100e11..10cd7d7 100644
--- a/exercices2.tex
+++ b/exercices2.tex
@@ -91,31 +91,127 @@ Git: \input{vcline.tex}
 %
 %
 
-\exercice
+\exercice\label{non-square-words-is-algebraic}
 
-Soit $\Sigma = \{a,b\}$.  Montrer que le langage $L := \{ww :
-w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (par exemple,
-$\varepsilon$, $aa$, $abab$, $abaaba$ ou encore $aabbaabb$) n'est pas
-algébrique.  On pourra pour considérer son intersection avec le
-langage $L_0$ dénoté par l'expression rationnelle $a{*}b{*}a{*}b{*}$
-et appliquer le lemme de pompage.
+Soit $\Sigma = \{a,b\}$.  On considère le langage $M$ des mots qui
+\emph{ne s'écrivent pas} sous la forme $ww$ avec $w\in\Sigma^*$
+(c'est-à-dire sous la forme d'un carré ; autrement dit, le langage $M$
+est le \emph{complémentaire} du langage $Q$ des carrés considéré dans
+l'exercice \ref{square-words-not-algebraic}) : par exemple, $M$
+contient les mots $a$, $b$, $ab$, $aab$ et $aabb$ mais pas
+$\varepsilon$, $aa$, $abab$ ni $abaaba$.
+
+(0) Expliquer pourquoi tout mot sur $\Sigma$ de longueur impaire est
+dans $M$, et pourquoi un mot $x_1\cdots x_{2n}$ de longueur paire $2n$
+est dans $M$ si et seulement si il existe $i$ tel que $x_i \neq
+x_{n+i}$.
+
+On considère par ailleurs la grammaire hors contexte $G$
+(d'axiome $S$)
+\[
+\begin{aligned}
+S &\rightarrow A \;|\; B \;|\; AB \;|\; BA\\
+A &\rightarrow a \;|\; aAa \;|\; aAb \;|\; bAa \;|\; bAb\\
+B &\rightarrow b \;|\; aBa \;|\; aBb \;|\; bBa \;|\; bBb\\
+\end{aligned}
+\]
+
+(1) Décrire le langage $L(G,A)$ des mots dérivant de $A$ dans la
+grammaire $G$ (autrement dit, le langage engendré par la grammaire
+identique à $G$ mais ayant pour axiome $A$).  Décrire de même
+$L(G,B)$.
+
+(2) Montrer que tout mot de longueur impaire est dans le
+langage $L(G)$ engendré par $G$.
+
+(3) Montrer que tout mot $t \in M$ de longueur paire est dans $L(G)$.
+(Indication : si $t = x_1\cdots x_{2n}$ est de longueur paire $2n$ et
+que $x_i \neq x_{n+i}$, on peut considérer la factorisation de $t$ en
+$x_1\cdots x_{2i-1}$ et $x_{2i}\cdots x_{2n}$.)
+
+(4) Montrer que tout mot de $L(G)$ de longueur paire est dans $M$.
+
+(5) En déduire que $M$ est algébrique.
 
 \begin{corrige}
-Supposons par l'absurde que $L$ soit algébrique : alors son
+(0) En remarquant que si $n = |w|$ alors $|ww| = 2n$, on constate que
+  tout mot de la forme $ww$ est de longueur paire, et de plus, que
+  pour un mot de longueur $2n$, être de la forme $ww$ signifie que son
+  préfixe de longueur $n$ soit égal à son suffixe de longueur $n$ ;
+  c'est-à-dire, si $t = x_1\cdots x_{2n}$, que $x_1\cdots x_n =
+  x_{n+1}\cdots x_{2n}$, ce qui signifie exactement $x_i = x_{n+i}$
+  pour tout $1\leq i\leq n$.
+
+(1) La règle $A \rightarrow a \,|\, aAa \,|\, aAb \,|\, bAa \,|\, bAb$
+  permet de faire à partir de $A$ une dérivation qui ajoute un nombre
+  quelconque de fois une lettre ($a$ ou $b$) de chaque part de $A$, et
+  finalement remplace ce $A$ par $a$.  On obtient donc ainsi
+  exactement les mots de longueur impaire ayant un $a$ comme lettre
+  centrale : $L(G,A) = \{w_1aw_2 : |w_1|=|w_2|\}$.  De même, $L(G,B) =
+  \{w_1bw_2 : |w_1|=|w_2|\}$.
+
+(2) Tout mot de longueur impaire est soit dans $L(G,A)$ soit dans
+  $L(G,B)$ selon que sa lettre centrale est un $a$ ou un $b$.  Il est
+  donc dans $L(G)$ en vertu des règles $S\rightarrow A$ et
+  $S\rightarrow B$.
+
+(3) Soit $t = x_1\cdots x_{2n}$ un mot de $M$ de longueur paire $2n$ :
+  d'après (0), il existe $i$ tel que $x_i \neq x_{n+i}$.  Posons alors
+  $u = x_1\cdots x_{2i-1}$ et $v = x_{2i}\cdots x_{2n}$.  Chacun de
+  $u$ et de $v$ est de longueur impaire.  De plus, leurs lettres
+  centrales sont respectivement $x_i$ et $x_{n+i}$, et elles sont
+  différentes : l'une est donc un $a$ et l'autre un $b$ ; mettons sans
+  perte de généralité que $x_i = a$ et $x_{n+i} = b$.  Alors $u \in
+  L(G,A)$ d'après (1) et $v \in L(G,B)$ : le mot $t = uv$ s'obtient
+  donc par la règle $S \rightarrow AB$ (suivie de dérivations de $u$ à
+  partir de $A$ et de $v$ a partir de $B$) : ceci montre bien $t \in
+  L(G)$.
+
+(4) On a vu en (1) que tout mot dérivant de $A$ ou de $B$ est de
+  longueur impaire.  Un mot $t$ de $L(G)$ de longueur paire dérive
+  donc forcément de $AB$ ou de $BA$.  Sans perte de généralité,
+  supposons qu'il dérive de $AB$, et on veut montrer qu'il appartient
+  à $M$.  Appelons $u$ le facteur de $t$ qui dérive de $A$ et $v$ le
+  facteur de $t$ qui dérive de $B$ : on sait alors (toujours
+  d'après (1)) que $u$ s'écrit sous la forme $x_1\cdots x_{2i-1}$ où
+  la lettre centrale $x_i$ vaut $a$, et que $v$ s'écrit sous la forme
+  (quitte à continuer la numérotation des indices) $x_{2i}\cdots
+  x_{2n}$ où la lettre centrale $x_{n+i}$ vaut $b$.  Alors $x_{n+i}
+  \neq x_i$ donc le mot $t$ n'est pas dans $L$ d'après (0).
+
+(5) On a $M = L(G)$ car d'après les questions précédentes, tout mot de
+  longueur impaire est dans les deux et qu'un mot de longueur paire
+  est dans l'un si et seulement si il est dans l'autre.  On a donc
+  montré que $M$ est algébrique.
+\end{corrige}
+
+
+\exercice\label{square-words-not-algebraic}
+
+Soit $\Sigma = \{a,b\}$.  Montrer que le langage $Q := \{ww :
+w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (autrement dit,
+des carrés ; par exemple, $\varepsilon$, $aa$, $abab$, $abaaba$ ou
+encore $aabbaabb$ sont dans $Q$) n'est pas algébrique.  On pourra pour
+considérer son intersection avec le langage $L_0$ dénoté par
+l'expression rationnelle $a{*}b{*}a{*}b{*}$ et appliquer le lemme de
+pompage.
+
+\begin{corrige}
+Supposons par l'absurde que $Q$ soit algébrique : alors son
 intersection avec le langage rationnel $L_0 = \{a^m b^n a^{m'} b^{n'} :
-m,n,m',n' \in \mathbb{N}\}$ est encore algébrique.  Or $L \cap L_0 =
+m,n,m',n' \in \mathbb{N}\}$ est encore algébrique.  Or $Q \cap L_0 =
 \{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$.  On va maintenant utiliser
 le lemme de pompage pour arriver à une contradiction.
 
 Appliquons le lemme de pompage pour les langages algébriques au
-langage $L \cap L_0 = \{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$
+langage $Q \cap L_0 = \{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$
 considéré : appelons $k$ l'entier dont le lemme de pompage garantit
 l'existence.  Considérons le mot $t := a^k b^k a^k b^k$ : dans la
 suite de cette démonstration, on appellera « bloc » de $t$ un des
 quatre facteurs $a^k$, $b^k$, $a^k$ et $b^k$.  D'après la propriété de
 $k$ garantie par le lemme de pompage, il doit exister une
 factorisation $t = uvwxy$ pour laquelle on a (i) $|vx|\geq 1$,
-(ii) $|vwx|\leq k$ et (iii) $uv^iwx^iy \in L \cap L_0$ pour
+(ii) $|vwx|\leq k$ et (iii) $uv^iwx^iy \in Q \cap L_0$ pour
 tout $i\geq 0$.
 
 Chacun de $v$ et de $x$ doit être contenu dans un seul bloc, i.e.,
@@ -133,14 +229,19 @@ D'après la propriété (i), au moins l'un de $v$ et de $x$ n'est pas le
 mot vide.  Si ce facteur non trivial est dans le premier bloc $a^k$,
 l'autre ne peut pas être dans l'autre bloc $a^k$ d'après ce qui vient
 d'être dit : donc $uv^iwx^iy$ est de la forme $a^{k'} b^n a^k b^k$
-avec $k'>k$ si $i>1$, qui n'appartient pas à $L\cap L_0$, une
+avec $k'>k$ si $i>1$, qui n'appartient pas à $Q\cap L_0$, une
 contradiction.  De même, le facteur non trivial est dans le premier
 bloc $b^k$, l'autre ne peut pas être dans l'autre bloc $b^k$ : donc
 $uv^iwx^iy$ est de la forme $a^m b^{k'} a^{m'} b^k$ avec $k'>k$ si
-$i>1$, qui n'appartient pas à $L\cap L_0$, de nouveau une
+$i>1$, qui n'appartient pas à $Q\cap L_0$, de nouveau une
 contradiction.  Les deux autres cas sont analogues.
 \end{corrige}
 
+\textbf{Remarque :} Les exercices \ref{non-square-words-is-algebraic}
+et \ref{square-words-not-algebraic} mis ensemble donnent un exemple
+explicite d'un langage $M$ algébrique dont le complémentaire $Q$ n'est
+pas algébrique.
+
 
 %
 %