diff options
| -rw-r--r-- | controle-20180322.tex | 109 |
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} % |