Third exercise on CFGs.

1 files changed, 30 insertions, 0 deletions

diff --git a/controle-20200123.tex b/controle-20200123.tex
index d77ec87..f87eb0e 100644
--- a/controle-20200123.tex
+++ b/controle-20200123.tex
@@ -232,6 +232,36 @@ nombre fini d'entiers naturels qui ne peuvent pas s'écrire sous la
 forme $\ell_1 m_1 + \cdots + \ell_r m_r$ avec $m_1,\ldots,m_r \in
 \mathbb{N}$, et, le cas échéant, les énumérer.
 
+
+%
+%
+%
+
+\exercice
+
+On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
+nonterminaux $N = \{S, T, U\}$ sur l'alphabet $\Sigma = \{a,b,c\}$
+donnée par
+\[
+\begin{aligned}
+S &\rightarrow T \;|\; TaS\\
+T &\rightarrow U \;|\; UbT\\
+U &\rightarrow c\\
+\end{aligned}
+\]
+(La grammaire en question est inambiguë : on ne demande pas de le
+démontrer.)
+
+(1) Donner les arbres d'analyse (= de dérivation) des mots suivants :
+$cacbcac$ et $cbcacbc$.
+
+(2) Expliquer pourquoi le langage $L := L(G)$ engendré par $G$ est, en
+fait, rationnel et donner une expression rationnelle qui le dénote.
+(On pourra commencer par décrire le langage $L' := L(G,T) := \{w \in
+\Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots qui dérivent
+de $T$ dans $G$.)
+
+
 %
 %
 %