From f39b25060c2a5692b1f838b251a8a2cc7a338c88 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 30 Jan 2018 18:59:33 +0100
Subject: Add an extra question.

---
 controle-20180206.tex | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 65 insertions(+), 1 deletion(-)

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}
+
 
 %
 %
-- 
cgit v1.2.3