Another example of CFG (too complicated?).

1 files changed, 44 insertions, 0 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index ee28534..af3404b 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3124,6 +3124,50 @@ VV'|\varepsilon$).  Nous éviterons ces extensions aux grammaires hors
 contexte pour ne pas introduire de confusion.
 
 
+\subsection{Autres exemples de grammaires hors contexte}
+
+\thingy Sur l'alphabet $\Sigma = \{a,b\}$, montrons que la grammaire
+$G$ donnée par
+\[
+S\; \rightarrow\;\; aSbS \;|\; bSaS \;|\; \varepsilon
+\]
+(c'est-à-dire $N = \{S\}$ où $S$ est l'axiome, et pour règles $S
+\rightarrow aSbS$ et $S \rightarrow bSaS$ et $S \rightarrow
+\varepsilon$) engendre le langage $L$ formé des mots ayant un nombre
+total de $a$ égal au nombre total de $b$, i.e., $L = \{w \in\Sigma^* :
+|w|_a = |w|_b\}$ où $|w|_x$ désigne le nombre total d'occurrences de
+la lettre $x$ dans le mot $w$.
+
+Dans un sens il est évident que tout pseudo-mot obtenu en dérivant $S$
+a un nombre de $a$ égal au nombre de $b$, puisque cette propriété est
+conservée par toute dérivation immédiate.  Autrement dit, $L(G)
+\subseteq L$.
+
+Pour ce qui est de la réciproque, on va montrer par récurrence sur
+$|w|$ que tout mot $w \in \Sigma^*$ ayant autant de $a$ que de $b$ est
+dans $L(G)$.  Pour $|w|=0$ c'est trivial.  Sinon, on peut supposer
+sans perte de généralité que le mot $w$ considéré commence par $a$,
+soit $w = aw'$ où $w'$ vérifie $|w'|_b - |w'|_a = 1$.  Considérons
+maintenant la fonction $h$ qui à un entier $k$ entre $0$ et $|w'|$
+associe le nombre de $b$ moins le nombre de $a$ dans le préfixe de
+longueur $k$ de $w'$ (i.e., parmi les $k$ premières lettres de $w'$) :
+cette fonction prend les valeurs $h(0) = 0$ et $h(|w'|) = 1$, et elle
+varie de $\pm 1$ à chaque fois (i.e., $h(i) = h(i-1) \pm 1$ selon que
+la $i$-ième lettre de $w'$ est $b$ ou $a$).  Soit $k_0$ le plus grand
+entier tel que $h(k_0) = 0$ : cet entier est bien défini car $h(0)=0$.
+On a forcément $h(k_0+1) = 1$ car l'autre possibilité, $h(k_0+1) = -1$
+impliquerait que $h$ devrait repasser par la valeur $0$ pour atteindre
+la valeur finale $h(|w'|) = 1$, ce qui contredirait la maximalité de
+$k_0$.  Bref, si $u$ est le préfixe de $w'$ de longueur $k_0$, on a
+$|u|_b - |u|_a = h(k_0) = 0$ et la lettre suivante de $w'$ est un $b$,
+si bien que $w' = ubv$ et finalement $w = aubv$ où $u$ et donc $v$ ont
+autant que $a$ que de $b$, i.e., appartiennent à $L$, et par
+récurrence (ils sont de longueur strictement plus courte que $w$)
+appartiennent à $L(G)$.  On peut donc dériver $u$ et $v$ de $S$, donc
+$w$ de $aSbS$, et comme $aSbS$ se dérive immédiatement de $S$, on a
+bien $w \in L(G)$, ce qui conclut la récurrence.
+
+
 
 %
 %