summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2018-01-30 17:59:33 (GMT)
committerDavid A. Madore <david+git@madore.org>2018-01-30 17:59:33 (GMT)
commitf39b25060c2a5692b1f838b251a8a2cc7a338c88 (patch)
tree3f517cf4d252628d8850f6d7d97e810391d1d439
parent4307a310373c44569f175d1cb2d5f5fad87fe19c (diff)
downloadinf105-f39b25060c2a5692b1f838b251a8a2cc7a338c88.zip
inf105-f39b25060c2a5692b1f838b251a8a2cc7a338c88.tar.gz
inf105-f39b25060c2a5692b1f838b251a8a2cc7a338c88.tar.bz2
Add an extra question.
-rw-r--r--controle-20180206.tex66
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}
+
%
%