Add an exercise on CFGs.

1 files changed, 78 insertions, 1 deletions

diff --git a/controle-20190205.tex b/controle-20190205.tex
index 166bb33..3802f51 100644
--- a/controle-20190205.tex
+++ b/controle-20190205.tex
@@ -96,6 +96,15 @@ Les exercices sont totalement indépendants.  Ils pourront être traités
 dans un ordre quelconque, mais on demande de faire apparaître de façon
 très visible dans les copies où commence chaque exercice.
 
+Dans l'exercice \ref{exercise-on-finite-automata}, les différentes
+questions dépendent les unes des autres : il est donc impératif de les
+traiter dans l'ordre, et il est conseillé de vérifier soigneusement
+chaque réponse avant de passer à la suite.  Dans
+l'exercice \ref{exercise-on-context-free-grammars}, les questions
+dépendent également les unes des autres, mais l'énoncé fournit toutes
+les informations nécessaires pour permettre de traiter la suite si on
+ne parvient pas à résoudre une question donnée.
+
 \medbreak
 
 L'usage de tous les documents (notes de cours manuscrites ou
@@ -122,7 +131,7 @@ Cet énoncé comporte \textcolor{red}{à remplir} (page de garde incluse)
 %
 %
 
-\exercice
+\exercice\label{exercise-on-finite-automata}
 
 Dans cet exercice, on pose $\Sigma = \{a,b\}$.
 
@@ -371,6 +380,74 @@ On pouvait aussi donner, entre autres choses :
 %
 %
 
+\exercice\label{exercise-on-context-free-grammars}
+
+On considère la grammaire hors-contexte $G$ d'axiome $S$ sur
+l'alphabet $\Sigma = \{a,b\}$ donnée par
+\[
+\begin{aligned}
+S &\rightarrow SaSbS\\
+S &\rightarrow \varepsilon\\
+\end{aligned}
+\]
+
+(1) Montrer que cette $G$ est ambiguë : pour cela, on exhibera deux
+arbres d'analyse différents du mot $abab$.
+
+\emph{Notation :} Si $w \in \Sigma^*$, on notera $|w|_a$ le nombre
+total d'occurrences de la lettre $a$ dans le mot $w$, et de façon
+analogue $|w|_b$ le nombre total d'occurrences de la lettre $b$ (on a
+bien sûr $|w| = |w|_a + |w|_b$ puisque $\Sigma = \{a,b\}$).
+
+On se propose, dans les quelques questions suivantes, de montrer que
+le langage $L := L(G)$ engendré par la grammaire $G$ est l'ensemble
+$M$ des mots $w \in \Sigma^*$ vérifiant les deux propriétés
+suivantes :
+\begin{itemize}
+\item[(A)] $|w|_b = |w|_a$, et
+\item[(B)] $|u|_b \leq |u|_a$ pour tout préfixe $u$ de $w$
+\end{itemize}
+(autrement dit, le nombre de $b$ de n'importe quel préfixe de $w$ est
+inférieur ou égal au nombre de $a$, et pour le mot $w$ tout entier il
+y a égalité).
+
+(2) Expliquer \emph{brièvement} pourquoi, si $w,w',w'' \in \Sigma^*$,
+alors tout préfixe du mot $waw'bw''$ est d'une des trois formes
+suivantes : (i) $u$ pour $u$ un préfixe de $w$, (ii) $wau'$ pour
+$u'$ un préfixe de $w'$, ou (iii) $waw'bu''$ pour $u''$ un préfixe
+de $w''$.  (On rappelle que le mot vide et le mot tout entier comptent
+pour préfixes d'un mot.)
+
+(3) Si $w,w',w'' \in \Sigma^*$ vérifient tous les trois la
+propriété (A) ci-dessus, montrer que c'est encore le cas
+de $waw'bw''$.  Si $w,w',w'' \in \Sigma^*$ vérifient tous les trois la
+propriété (B) ci-dessus, montrer que c'est encore le cas
+de $waw'bw''$ (on utilisera pour cela la question (2)).
+
+(4) Déduire de la question (3) que tout mot de $L$ vérifie (A) et (B).
+(Autrement dit, on vient de montrer : $L \subseteq M$.)
+
+(5) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B) : montrer
+qu'on peut écrire $w = av$ pour un certain $v \in \Sigma^*$ ; si $w'$
+est le plus long préfixe de $v$ vérifiant (B), montrer que $w =
+aw'bw''$ où $w'$ et $w''$ vérifient tous les deux (A) et (B).
+
+(6) Déduire de la question (5) que tout mot vérifiant (A) et (B)
+appartient à $L$.  (Autrement dit, on vient de montrer : $M \subseteq
+L$.  On a donc $L = M$.)
+
+(7) En notant $N = \{a^i b^j : i,j\in\mathbb{N}\}$ le langage défini
+par l'expression rationnelle $a{*}b{*}$, et en utilisant la
+description qu'on vient de trouver pour $L$ (comme l'ensemble des mots
+vérifiant (A) et (B)), déterminer $L \cap N$.  Est-il rationnel ?
+
+(8) Le langage $L$ est-il rationnel ?
+
+
+%
+%
+%
+
 \exercice
 
 On rappelle la définition du problème de l'arrêt : c'est l'ensemble