summaryrefslogtreecommitdiffstats log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiff
Diffstat (limited to 'controle-20180322.tex')
-rw-r--r--controle-20180322.tex109
1 files changed, 106 insertions, 3 deletions
 diff --git a/controle-20180322.tex b/controle-20180322.texindex 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>b.S>+\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+% Sb.S>>+\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} %