diff options
| -rw-r--r-- | controle-20180206.tex | 66 |
1 files changed, 65 insertions, 1 deletions
diff --git a/controle-20180206.tex b/controle-20180206.tex index f031fb6..3db067b 100644 --- a/controle-20180206.tex +++ b/controle-20180206.tex @@ -110,7 +110,7 @@ Durée : 1h30 Barème \emph{indicatif} : 7 points par exercice \ifcorrige -Ce corrigé comporte 8 pages (page de garde incluse) +Ce corrigé comporte 9 pages (page de garde incluse) \else Cet énoncé comporte 4 pages (page de garde incluse) \fi @@ -475,6 +475,70 @@ s'associe-t-elle\footnote{On dit qu'une opération binaire $\boxdot$ d'analyse (d) de la question (1) montre que $@$ s'associe à droite. \end{corrige} +\smallskip + +(La question (3) est indépendante de (1) et (2). Par ailleurs, on +pourra, si on souhaite s'épargner des confusions, choisir d'appeler +$a$ la lettre « parenthèse ouvrante » de $\Sigma$ et $b$ la lettre +« parenthèse fermante » afin de les distinguer des parenthèses +mathématiques.) + +(3) Soit $L = L(G)$ le langage engendré par $G$. Soit $M$ le langage +des mots sur $\Sigma$ formés d'un certain nombre de parenthèses +ouvrantes, puis de la lettre $x$, puis d'un certain nombre +(possiblement différent) de parenthèses ouvrantes : autrement dit, des +mots de la forme « ${(}^i\, x\, {)}^j$ », où on a noté « ${(}^i$ » une +succession de $i$ parenthèses ouvrantes et « ${)}^j$ » une succession +de $j$ parenthèses fermantes (on pourra noter ce mot $a^i x b^j$ si on +préfère).\quad (a) Décrire le langage $L\cap M$ (des mots de $L$ qui +appartiennent aussi à $M$).\quad (b) Ce langage $L\cap M$ est-il +rationnel ?\quad (c) Le langage $L$ est-il rationnel ? + +\begin{corrige} +(a) Cherchons pour quelles valeurs $(i,j) \in \mathbb{N}^2$ le mot + « ${(}^i\, x\, {)}^j$ » de $M$ appartient à $L$. La dérivation $S + \rightarrow T \rightarrow U \rightarrow (S) \rightarrow (T) + \rightarrow (U) \rightarrow ((S)) \rightarrow \cdots + \rightarrow{(}^i\, S\, {)}^i \rightarrow{(}^i\, T\, {)}^i + \rightarrow{(}^i\, U\, {)}^i \rightarrow{(}^i\, V\, {)}^i + \rightarrow{(}^i\, x\, {)}^i$ montre que c'est le cas si $j=i$, + autrement dit s'il y a autant de parenthèses fermantes qu'ouvrantes. + Mais réciproquement, la propriété d'avoir autant de parenthèses + fermantes qu'ouvrantes est préservée par toutes les productions + de $G$ (et est satisfaite par l'axiome), donc est vérifiée par tout + mot de $L=L(G)$. On a donc prouvé que le $L\cap M$ est l'ensemble + des mots de la forme « ${(}^i\, x\, {)}^i$ » où $i\in \mathbb{N}$. + +(b) Le langage $L\cap M$ constitué des mots de la forme « ${(}^n\, + x\, {)}^n$ » où $i\in \mathbb{N}$ n'est pas rationnel. Cela résulte + du lemme de pompage (presque exactement comme l'exemple du langage + $\{a^n b^n : i\in\mathbb{N}\}$ donné en cours) : donnons l'argument + en remplaçant la parenthèse ouvrante par $a$ et la parenthèse + fermante par $b$ pour plus de clarté notationnelle. Appliquons le + lemme de pompage pour les langages rationnels au langage $L \cap M = + \{a^n x b^n : i\in\mathbb{N}\}$ supposé par l'absurde être + rationnel : appelons $k$ l'entier dont le lemme de pompage garantit + l'existence. Considérons le mot $t := a^k x b^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 L\cap M$ 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 x b^k$ est de cette forme) ; disons $u = a^\ell$ et $v = + a^m$, si bien que $w = a^{k-\ell-m} x 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 à $L\cap M$ ; mais dès que + $i\neq 1$, ceci est faux : il suffit donc de prendre $i=0$ pour + avoir une contradiction. + +(c) Le langage $M$ est rationnel puisqu'il est dénoté par l'expression + rationnelle $a{*}xb{*}$ (toujours en notant $a$ la parenthèse + ouvrante et $b$ la parenthèse fermante). Si le langage $L$ était + rationnel, le langage $L\cap M$ le serait aussi (on sait que + l'intersection de deux langages rationnels est rationnelle), ce qui + n'est pas le cas d'après la question (b). Le langage $L$ n'est donc + pas rationnel. +\end{corrige} + % % |