diff options
| -rw-r--r-- | exercices2.tex | 127 |
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. + % % |