diff options
| -rw-r--r-- | controle-20200123.tex | 30 |
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$.) + + % % % |