diff options
| -rw-r--r-- | controle-20170207.tex | 38 |
1 files changed, 38 insertions, 0 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex index 81fea55..7a941e5 100644 --- a/controle-20170207.tex +++ b/controle-20170207.tex @@ -531,6 +531,44 @@ l'indécidabilité du problème de l'arrêt. \end{corrige} +% +% +% + +\exercice + +On considère la grammaire hors-contexte $G$ d'axiome $S$ sur +l'alphabet $\Sigma = \{a,b,c\}$ donnée par +\[ +\begin{aligned} +S &\rightarrow TS \;|\; \varepsilon\\ +T &\rightarrow aSbSc\\ +\end{aligned} +\] +On notera $L(G) = L(G,S)$ le langage qu'elle engendre, et $L(G,T)$ le +langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère le +langage engendré par la grammaire identique à $G$ mais ayant $T$ pour +axiome). + +(1) Comment décrire $L(G)$ simplement en fonction de $L(G,T)$ ? Y +a-t-il inclusion de l'un dans l'autre ? + +(2) Montrer que tout mot $w$ de $L(G)$ a le même nombre de $a$, de $b$ +et de $c$, c'est-à-dire $|w|_a = |w|_b = |w|_c$ où $|w|_x$ désigne le +nombre total d'occurrences de la lettre $x$ dans le mot $w$. + +(3) Montrer que si $u'$ est un mot de $L(G,T)$ et $u$ un préfixe +strict de $u'$ (c'est-à-dire, un préfixe différent de $u'$ lui-même), +alors $|u|_c < |u|_a$ ; en déduire qu'il n'appartient pas à $L(G,T)$. +En d'éduire que si $u \in L(G,T)$ et $z \in \Sigma^+$ (c'est-à-dire +$z\in\Sigma^*$ et $z\neq\varepsilon$) alors $uz \not\in L(G,T)$. + +(4) En déduire que si un mot $w$ s'écrit $w = u_1\cdots u_k$ avec +$u_1,\ldots,u_k \in L(G,T)$ alors cette factorisation est unique. + +(5) En déduire que la grammaire $G$ est inambiguë. + + % % |