diff options
| -rw-r--r-- | notes-inf105.tex | 44 |
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. + + % % |