Various examples of CFGs (not necessarily interesting).

1 files changed, 136 insertions, 2 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index af3404b..b87818d 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3123,13 +3123,125 @@ nonterminal $V'$ en $T \rightarrow UV'$ et $V' \rightarrow
 VV'|\varepsilon$).  Nous éviterons ces extensions aux grammaires hors
 contexte pour ne pas introduire de confusion.
 
+\thingy Il peut être utile, pour raisonner sur les langages
+algébriques, d'introduire, lorsque $G$ est une grammaire hors contexte
+et $T$ un nonterminal quelconque, le langage $L(G,T)$ des mots qui
+dérivent de $T$, c'est-à-dire le langage engendré par la grammaire
+$G'$ identique à $G$ à ceci près que son axiome est $T$.
+
+On a alors $L(G) = L(G,S)$ où $S$ est l'axiome de $G$, et chaque règle
+de production $T \rightarrow \alpha_1 | \cdots | \alpha_n$ se traduit
+par une équation portant sur $L(G,T)$, par exemple $T \rightarrow aUbV
+| cW$ implique $L(G,T) = a\, L(G,U)\, b\, L(G,V) \; \cup \; c L(G,W)$.
+De cette manière, une grammaire hors contexte donne lieu à un système
+d'équations portant sur des langages (par exemple, la grammaire de
+\ref{basic-example-context-free-grammar} donne lieu à l'équation $L(G)
+= (a\,L(G)\,b) \cup \{\varepsilon\}$ : on peut montrer que la
+définition des grammaires hors contexte revient à considérer la plus
+petite (au sens de l'inclusion) solution de ce système d'équations.
+
 
 \subsection{Autres exemples de grammaires hors contexte}
 
+\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire
+(d'axiome $S$)
+\[
+\begin{aligned}
+S &\rightarrow AT\\
+A &\rightarrow aA \;|\; \varepsilon\\
+T &\rightarrow aTb \;|\; \varepsilon\\
+\end{aligned}
+\]
+Il est clair que le langage $L(G,A)$ des mots qui dérivent de $A$ est
+simplement $\{a\}^* = \{a^i : i\in\mathbb{N}\}$ ; et le langage
+$L(G,T)$ est $\{a^j b^j : j\in\mathbb{N}\}$ comme
+en \ref{basic-example-context-free-grammar}.  Le langage $L(G) =
+L(G,A)\, L(G,T)$ est donc $\{a^i b^j : i \geq j\}$, l'ensemble des
+mots de la forme $a^i b^j$ pour lesquels $i \geq j$.  (Ce langage est
+intéressant sur le plan théorique, car bien qu'il soit algébrique et
+ici défini par une grammaire inambiguë, il ne peut pas être analysé
+par un analyseur LL.)
+
+On peut aussi considérer la grammaire $G'$ définie par
+\[
+\begin{aligned}
+S &\rightarrow T \;|\; aS\\
+T &\rightarrow aTb \;|\; \varepsilon\\
+\end{aligned}
+\]
+Il n'est pas difficile de se convaincre qu'elle engendre le même
+langage $L(G)$ que la précédente (elle est donc faiblement équivalente
+à $G$).
+
+\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire
+(d'axiome $S$)
+\[
+\begin{aligned}
+S &\rightarrow U \;|\; V \;|\; \varepsilon\\
+U &\rightarrow aUb \;|\; ab\\
+V &\rightarrow aVbb \;|\; abb\\
+\end{aligned}
+\]
+Il est clair que le langage $L(G,U)$ des mots qui dérivent de $U$ est
+$\{a^i b^i : i>0\}$ comme en \ref{basic-example-context-free-grammar},
+et de façon analogue, le langage $L(G,V)$ des mots qui dérivent de $V$
+est $\{a^i b^{2i} : i>0\}$.  Le langage $L(G) = L(G,U) \cup L(G,V)$
+est donc l'ensemble des mots de la forme $a^i b^j$ où $j=i$ \emph{ou
+  bien} $j=2i$.  (Ce langage est intéressant sur le plan théorique,
+car bien qu'il soit algébrique et défini par une grammaire inambiguë,
+il n'est pas analysable par un automate à pile déterministe.)
+
+\thingy Sur l'alphabet $\Sigma = \{a,b,c\}$, considérons la grammaire
+(d'axiome $S$)
+\[
+\begin{aligned}
+S &\rightarrow UC \;|\; AV\\
+A &\rightarrow aA \;|\; \varepsilon\\
+C &\rightarrow cC \;|\; \varepsilon\\
+U &\rightarrow aUb \;|\; \varepsilon\\
+V &\rightarrow bVc \;|\; \varepsilon\\
+\end{aligned}
+\]
+Il est clair que le langage $L(G,A)$ des mots qui dérivent de $A$ est
+simplement $\{a\}^* = \{a^i : i\in\mathbb{N}\}$ et que le langage
+$L(G,C)$ des mots qui dérivent de $C$ est simplement $\{c\}^* = \{c^j
+: j\in\mathbb{N}\}$ ; le langage $L(G,U)$ est $\{a^i b^i :
+i\in\mathbb{N}\}$ comme en \ref{basic-example-context-free-grammar},
+et de même $L(G,V) = \{b^j c^j : j\in\mathbb{N}\}$.  Finalement, $L(G)
+= L(G,U)\,L(G,C) \;\cup\; L(G,A)\,L(G,V)$ montre que $L(G) = \{a^i b^i
+c^j : i,j\in\mathbb{N}\} \cup \{a^i b^j c^j : i,j\in\mathbb{N}\}$ est
+le langage des mots de la forme $a^i b^r c^j$ où $r=i$ \emph{ou}
+$r=j$.  (Ce langage est intéressant sur le plan théorique, car il est
+algébrique mais « intrinsèquement ambigu ».)
+
+\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire
+(d'axiome $S$)
+\[
+S\; \rightarrow\; aSbS \;|\; \varepsilon
+\]
+ou, ce qui revient au même
+\[
+\begin{aligned}
+S &\rightarrow TS \;|\; \varepsilon\\
+T &\rightarrow aSb\\
+\end{aligned}
+\]
+(la première ligne revient par ailleurs à $S \rightarrow T^*$).  On a
+alors $L(G) = L(G,T)^*$ où $L(G,T) = a\, L(G)\, b$ désigne le langage
+des mots qui peuvent être dérivés à partir de $T$.
+
+Ce langage $L(G)$ s'appelle langage des \textbf{expressions
+  bien-parenthésées} où $a$ représente une parenthèse ouvrante et $b$
+une parenthèse fermante (et $L(G,T)$ est le langage des blocs
+parenthésés : autrement dit, une expression bien-parenthésée est une
+suite de blocs parenthésés, et un bloc parenthésé est une expression
+bien-parenthésée entourée par une parenthèse ouvrante et une
+parenthèse fermante — c'est ce que traduit la grammaire).
+
 \thingy Sur l'alphabet $\Sigma = \{a,b\}$, montrons que la grammaire
-$G$ donnée par
+$G$ (d'axiome $S$) donnée par
 \[
-S\; \rightarrow\;\; aSbS \;|\; bSaS \;|\; \varepsilon
+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
@@ -3167,6 +3279,28 @@ 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.
 
+Un raisonnement analogue montre que la grammaire $G'$ donnée par
+\[
+\begin{aligned}
+S &\rightarrow aUbS \;|\; bVaS \;|\; \varepsilon\\
+U &\rightarrow aUbU\\
+V &\rightarrow bVaV\\
+\end{aligned}
+\]
+engendre le même langage $L = \{w \in\Sigma^* : |w|_a = |w|_b\}$ que
+ci-dessus (elle est donc faiblement équivalente à $G$) : l'idée est
+que le langage $L(G,U)$ des mots qui dérivent de $U$ est l'ensemble
+des expressions bien-parenthésées où $a$ est la parenthèse ouvrante et
+$b$ la fermante (dans le raisonnement ci-dessus, ce sont les mots pour
+lesquels la fonction $h$, partant de $0$, revient à $0$, et reste
+toujours positive ou nulle), tandis que $L(G,V)$ est l'ensemble des
+expressions bien-parenthésées où $b$ est la parenthèse ouvrante et $a$
+la fermante (la fonction $h$ reste toujours négative ou nulle), et
+tout mot de $L$ peut s'écrire comme concaténation de tels mots (en
+divisant selon le signe de $h$).  Une différence entre $G$ et $G'$ est
+que la grammaire $G$ est ambiguë (un terme qui sera défini plus bas)
+tandis que $G'$ ne l'est pas.
+
 
 
 %