summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2020-01-21 12:12:35 +0100
committerDavid A. Madore <david+git@madore.org>2020-01-21 12:12:35 +0100
commite4cd0ae069ad0a3495d87693518466ca6ca5a5fb (patch)
tree25ccd0ee84032f7635eb8311533ca18f34aadcb5
parent2f36233558948bb9771fab7f9bfa24c0fe4b6d04 (diff)
downloadinf105-e4cd0ae069ad0a3495d87693518466ca6ca5a5fb.tar.gz
inf105-e4cd0ae069ad0a3495d87693518466ca6ca5a5fb.tar.bz2
inf105-e4cd0ae069ad0a3495d87693518466ca6ca5a5fb.zip
Third exercise on CFGs.
-rw-r--r--controle-20200123.tex30
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$.)
+
+
%
%
%