diff options
| -rw-r--r-- | controle-20180322.tex | 40 |
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. + % % |