From bbdce8f028e3f1f8bcbcd0da036d6ab6f1a01808 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 31 Jan 2017 22:50:10 +0100
Subject: Write another exercise (without answers).

---
 controle-20170207.tex | 38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

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ë.
+
+
 
 %
 %
-- 
cgit v1.2.3