Answers to second exercise.

1 files changed, 106 insertions, 3 deletions

diff --git a/controle-20180322.tex b/controle-20180322.tex
index 8ecc787..20ef61e 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -341,11 +341,49 @@ S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\
 \end{aligned}
 \]
 
+Les questions de cet exercice sont essentiellement indépendantes, si
+ce n'est que la question (6) fait appel à la conclusion (énoncée) des
+questions (2) à (5).
+
+\smallskip
+
 (1) Donner deux arbres d'analyse (pour $G$) différents du mot $aab$.
 Que peut-on dire de la grammaire $G$ ?
 
-L'objet des questions suivantes (qui ne dépendent pas de la
-précédente) est de montrer que $L$ n'est pas rationnel.
+\begin{corrige}
+On peut proposer les arbres d'analyse suivants :\\
+% S<a.S<a.S<e.>>b.S<e.>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (42.500bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (30.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S2) -- (e0);
+\node (b0) at (60.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (S3) at (80.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S3);
+\node (e1) at (80.000bp,-50.000bp) [draw=none] {$\varepsilon$};  \draw (S3) -- (e1);
+\end{tikzpicture}
+d'une part,\hfill et
+% S<a.S<a.S<e.>b.S<e.>>>
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (25.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (50.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (a1) at (20.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (40.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (e0) at (40.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S2) -- (e0);
+\node (b0) at (60.000bp,-60.000bp) [draw=none] {$b$};  \draw (S1) -- (b0);
+\node (S3) at (80.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S3);
+\node (e1) at (80.000bp,-80.000bp) [draw=none] {$\varepsilon$};  \draw (S3) -- (e1);
+\end{tikzpicture}
+d'autre part\\
+(en fait, on peut se convaincre que ce sont les seuls possibles).
+La grammaire $G$ est donc ambiguë.
+\end{corrige}
+
+L'objet des questions suivantes est de montrer que $L$ n'est pas
+rationnel.
 
 Soit $M$ le langage $\{a^i b^j : i,j\in\mathbb{N}\}$ constitué des
 mots de la forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels
@@ -353,6 +391,10 @@ quelconques.
 
 (2) Donner une expression rationnelle qui dénote $M$.
 
+\begin{corrige}
+Le langage $M$ est dénoté par l'expression rationnelle $a{*}b{*}$.
+\end{corrige}
+
 Soit $P$ le langage $\{a^i b^j : i\geq j\}$ constitué des mots de la
 forme $a^i b^j$ avec $i$ et $j$ deux entiers naturels vérifiant $i\geq
 j$ (autrement dit, les mots de $M$ qui ont au moins autant de $a$ que
@@ -360,11 +402,72 @@ de $b$).
 
 (3) Montrer que $P \subseteq L$.
 
+\begin{corrige}
+Soient $i\geq j$ deux entiers naturels : on va expliquer comment
+produire le mot $a^i b^j$ selon les règles de $G$.  À partir de
+l'axiome $S$, on commence par appliquer $i-j$ fois la règle $a
+\rightarrow aS$, ce qui donne $a \Rightarrow aS \Rightarrow aaS
+\Rightarrow \cdots \Rightarrow a^{i-j} S$.  Appliquons maintenant $j$
+fois la règle $S\rightarrow aSbS$, suivie à chaque fois de
+$S\rightarrow\varepsilon$ sur le $S$ de droite : on obtient ainsi
+$a^{i-j} S \Rightarrow a^{i-j+1} S bS \Rightarrow a^{i-j+1} S b
+\Rightarrow a^{i-j+2} S b S b \Rightarrow a^{i-j+2} S bb \Rightarrow
+\cdots \Rightarrow a^i S b^j$.  Il suffit de terminer par une
+application de $S \rightarrow \varepsilon$ : on obtient ainsi une
+dérivation $S \mathrel{\Rightarrow^*} a^i b^j$ qui prouve que $a^i b^j
+\in L$.
+\end{corrige}
+
 (4) Montrer que $L\cap M \subseteq P$.
 
+\begin{corrige}
+Considérons la propriété « avoir (au total) au moins autant de $a$ que
+de $b$ », si on veut $|\xi|_a\geq |\xi|_b$, sur un pseudo-mot $\xi$
+(un « pseudo-mot » signifiant, par définition, un mot sur $\Sigma\cup
+N = \{a,b,S\}$).  Cette propriété est vérifiée par le pseudo-mot $S$.
+Elle est préservée si on remplace $S$ par $aSbS$ ou $aS$ ou
+$\varepsilon$ puisque dans chacun de ces cas le nombre de $a$ augmente
+d'au moins autant que le nombre de $b$.  Elle est donc possédée par
+tout pseudo-mot, et en particulier tout mot, qui dérive de $S$
+selon $G$.  On vient donc de prouver que tout mot de $L$ a au moins
+autant de $a$ que de $b$.  Notamment, tout mot de $L\cap M$ est un mot
+de la forme $a^i b^j$ (par définition de $M$), et qui vérifie $i\geq
+j$ (c'est ce qu'on vient de prouver).  Il est donc dans $P$.
+\end{corrige}
+
 (5) Montrer que $P$ n'est pas rationnel.
 
-(6) Déduire des questions (2) à (5) que $L$ n'est pas rationnel.
+\begin{corrige}
+Supposons par l'absurde que $P = \{a^i b^j : i\geq j\}$ soit
+rationnel.  Appliquons le lemme de pompage pour les langages
+rationnels au langage $P$ : appelons $k$ l'entier dont le lemme de
+pompage garantit l'existence.  Considérons le mot $t := a^k b^k$ (qui
+appartient bien à $P$ et est bien de longueur $\geq k$) : il doit
+alors exister une factorisation $t = uvw$ pour laquelle on a
+(i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in P$ pour
+tout $i\geq 0$.  La propriété (ii) assure que $uv$ est formé d'un
+certain nombre de répétitions de la lettre $a$ (car tout préfixe de
+longueur $\leq k$ de $a^k b^k$ est de cette forme) ; disons $u =
+a^\ell$ et $v = a^m$, si bien que $w = a^{k-\ell-m} b^k$.  La
+propriété (i) donne $m\geq 1$.  Enfin, la propriété (iii) affirme que
+le mot $uv^iw = a^{k+(i-1)m} x b^k$ appartient à $P$ ; or pour $i=0$,
+ceci est faux puisque $a^{k-m} b^k$ vérifie $k-m < k$.  On a donc
+abouti à une contradiction, et c'est que $P$ n'est pas rationnel.
+\end{corrige}
+
+(6) Déduire des questions (2) à (5) que $L$ n'est pas rationnel (on
+explicitera très soigneusement le raisonnement).
+
+\begin{corrige}
+On a vu à la question (3) que $P \subseteq L$ ; il est par ailleurs
+trivial que $P \subseteq M$, et on a donc $P \subseteq L\cap M$.  Mais
+on a vu à la question (4) que $L\cap M \subseteq P$ : on a donc $L\cap
+M \subseteq P$.  Le langage $M$ est rationnel d'après la question (2).
+Si le langage $L$ était lui aussi rationnel, le langage $L\cap M$
+(c'est-à-dire $P$) le serait car l'intersection de deux langages
+rationnels est rationnelle.  Or on a vu à la question (5) que $P$
+n'est pas rationnel.  C'est donc que $L$ ne l'est pas.
+\end{corrige}
 
 
 %