summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-12 16:02:04 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-12 16:02:04 (GMT)
commitabc511f93221e1cbb463df515f065b5e3a6f705d (patch)
tree6bebcce519602d3c71d53df00a8498627c89f30f
parent015c498faaae339ed54c3bf698ab98ab9f83d768 (diff)
downloadinf105-abc511f93221e1cbb463df515f065b5e3a6f705d.zip
inf105-abc511f93221e1cbb463df515f065b5e3a6f705d.tar.gz
inf105-abc511f93221e1cbb463df515f065b5e3a6f705d.tar.bz2
An algebraic language whose complement is not algebraic (the language of non-squares).
-rw-r--r--exercices2.tex127
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.
+
%
%