Add an exercise on formal grammars.

1 files changed, 40 insertions, 0 deletions

diff --git a/controle-20180322.tex b/controle-20180322.tex
index 516cd07..a1eb15e 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -140,6 +140,46 @@ résultant.
 états, déterminer une expression rationnelle dénotant le langage $M$.
 
 
+%
+%
+%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On appelle $L = L(G)$
+le langage défini par la hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par
+\[
+\begin{aligned}
+S &\rightarrow aSbS \;|\; aS \;|\; \varepsilon\\
+\end{aligned}
+\]
+
+(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.
+
+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
+quelconques.
+
+(2) Donner une expression rationnelle qui dénote $M$.
+
+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
+de $b$).
+
+(3) Montrer que $P \subseteq L$.
+
+(4) Montrer que $L\cap M \subseteq P$.
+
+(5) Montrer que $P$ n'est pas rationnel.
+
+(6) Déduire des questions (2) à (5) que $L$ n'est pas rationnel.
+
 
 %
 %