Context-free grammars and languages: definition and example.

1 files changed, 165 insertions, 12 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 57a9267..c8b4703 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -106,7 +106,7 @@ appelleront un \textbf{alphabet}, et qui correspond pour les
 informaticiens à un \textbf{jeu de caractères}.  Il s'agit d'un
 ensemble \emph{fini}, sans structure particulière, dont les éléments
 s'appellent \textbf{lettres}, ou encore \textbf{caractères} dans une
-terminologie plus informatique.
+terminologie plus informatique, ou parfois aussi \textbf{symboles}.
 
 Les exemples mathématiques seront souvent donnés sur un alphabet tel
 que l'alphabet à deux lettres $\{a,b\}$ ou à trois lettres
@@ -873,7 +873,7 @@ pour chaque $q\in F$ une flèche pointant de $q$ vers nulle
 part\footnote{Certains auteurs préfèrent d'autres conventions, par
   exemple celle consistant à entourer deux fois les états finaux.}.
 
-Lorsque plusieurs arêtes étiquetées par des symboles $x,y$ différents
+Lorsque plusieurs arêtes étiquetées par des lettres $x,y$ différentes
 relient les mêmes sommets $q,q'$ (i.e., lorsqu'on a à la fois
 $\delta(q,x) = q'$ et $\delta(q,y) = q'$), on pourra écrire « $x,y$ »
 ou « $x|y$ » sur l'arête en question (et ne la tracer qu'une seule
@@ -924,7 +924,7 @@ Graphiquement, on peut présenter la procédure de la manière suivante :
 on part de l'état $q_0$ (sommet du graphe représentant l'automate)
 indiqué par la flèche entrante (pointant de nulle part), et pour
 chaque lettre du mot $w = x_1\cdots x_n$ considéré, on suit l'arête
-portant ce symbole (et partant de l'état où on se trouve
+portant cette lettre pour étiquette (et partant de l'état où on se trouve
 actuellement).  Si à la fin l'état $q_n$ est acceptant (représenté par
 une flèche pointant vers nulle part), le mot $w$ est accepté, sinon il
 est rejeté.
@@ -1080,7 +1080,7 @@ partant de $q$ et étiquetée par $x$.
 
 \thingy Le fonctionnement d'un DFAI est le même que celui d'un DFA, à
 la modification suivante près : si on donne à consommer à l'automate
-un symbole pour lequel la transition n'est pas définie, i.e., s'il
+une lettre pour laquelle la transition n'est pas définie, i.e., s'il
 rencontre un $x$ pendant qu'il se trouve dans un état $q$ pour lequel
 $\delta(q,x)$ n'est pas défini, alors l'automate cesse de
 fonctionner : l'automate n'a plus d'état, n'effectue plus de
@@ -1250,7 +1250,7 @@ les automates finis déterministes comme étant complets, d'autres comme
   Q \times \Sigma \times Q$).
 \end{itemize}
 Autrement dit, on autorise maintenant un ensemble quelconque d'états
-initiaux, et de même, au lieu qu'un état $q$ et un symbole $x$
+initiaux, et de même, au lieu qu'un état $q$ et une lettre $x$
 déterminent un unique état $q' = \delta(q,x)$, on a maintenant affaire
 à un ensemble quelconque de triplets $(q,x,q')$.
 
@@ -1280,15 +1280,15 @@ chaque $1\leq i\leq n$.
 Il existe plusieurs manières de reformuler ce comportement : on peut
 par exemple dire que l'automate est dans plusieurs états à la fois,
 qu'il commence dans tous les états initiaux à la fois, et qu'à chaque
-fois qu'il consomme un symbole $x$, il effectue toutes les transitions
-possibles à partir d'un état où et étiquetées par ce symbole, et qu'au
-bout du compte l'automate accepte le mot lorsqu'il est dans \emph{au
-  moins un} état acceptant (même s'il est, par ailleurs, dans d'autres
-états).  C'est cette façon de voir les choses qui conduira à
+fois qu'il consomme une lettre $x$, il effectue toutes les transitions
+possibles à partir d'un état où et étiquetées par cette lettre, et
+qu'au bout du compte l'automate accepte le mot lorsqu'il est dans
+\emph{au moins un} état acceptant (même s'il est, par ailleurs, dans
+d'autres états).  C'est cette façon de voir les choses qui conduira à
 l'équivalence entre NFA et DFA (cf. \ref{determinization-of-nfa}).
 
 Une autre façon de présenter les choses est que l'automate « devine »
-par quel état initial commencer, et à chaque symbole consommé,
+par quel état initial commencer, et à chaque lettre consommée,
 « devine » quelle transition effectuer, de manière à accepter le mot
 si c'est possible.
 
@@ -2440,7 +2440,7 @@ $L$ n'est pas rationnel est donc quelque chose comme ceci :
 
 Donnons maintenant un exemple d'utilisation du lemme :
 
-\begin{prop}
+\begin{prop}\label{example-of-pumping-lemma}
 Soit $\Sigma = \{a,b\}$.  Le langage $L = \{a^n b^n : n\in\mathbb{N}\}
 = \{\varepsilon, ab, aabb, aaabbb,\ldots\}$ constitué des mots formés
 d'un certain nombre ($n$) de $a$ suivis du même nombre de $b$ n'est
@@ -2834,6 +2834,159 @@ et les langages reconnus sont les mêmes.
 \end{proof}
 
 
+\section{Grammaires hors contexte}
+
+\subsection{Définition, notations, exemples}
+
+\thingy\label{definition-context-free-grammar} Une \textbf{grammaire
+  hors contexte} (on dit parfois aussi « sans contexte » ; en anglais,
+« context-free grammar » ou « CFG ») sur un alphabet $\Sigma$ est la
+donnée
+\begin{itemize}
+\item d'un second alphabet $N$, disjoint de $\Sigma$, appelé ensemble
+  des \textbf{nonterminaux},
+\item d'un élément $S \in N$ appelé \textbf{axiome} ou \textbf{symbole
+  initial} de la grammaire,
+\item d'un ensemble \emph{fini} $R \subseteq N \times (\Sigma\cup
+  N)^*$ de couples $(T,\alpha)$ où $T$ est un nonterminal et $\alpha$
+  un mot sur l'alphabet $\Sigma\cup N$, les éléments $(T,\alpha)$ de
+  $R$ étant appelés les \textbf{règles} ou \textbf{productions} de la
+  grammaire.
+\end{itemize}
+
+\thingy Une grammaire hors contexte fait donc intervenir deux
+alphabets : l'alphabet $\Sigma$ sur lequel sera le langage (encore à
+définir), et l'alphabet $N$ (disjoint de $\Sigma$) qui intervient dans
+la définition de la grammaire.  Pour fixer la terminologie, on
+appellera \textbf{symbole} un élément de $\Sigma \cup N$, ces symboles
+étant dits \textbf{terminaux} lorsqu'ils appartiennent à $\Sigma$ (ou
+simplement « lettres »), et \textbf{nonterminaux} lorsqu'ils
+appartiennent à $N$.  Un mot sur $\Sigma\cup N$ (c'est-à-dire, une
+suite finie de symboles) sera appelé \textbf{pseudo-mot}, tandis que
+le terme « mot » sans précision supplémentaire sera utilisé pour
+désigner un mot sur $\Sigma$ (autrement dit, un mot est un pseudo-mot
+ne comportant que des symboles terminaux).
+
+Typographiquement, on aura tendance à utiliser des lettres minuscules
+pour désigner les symboles terminaux, et majuscules pour désigner les
+symboles nonterminaux ; et on aura tendance à utiliser des lettres
+grecques minuscules pour désigner les pseudo-mots.
+
+\thingy Intuitivement, il faut comprendre la grammaire de la manière
+suivante.  Les règles $(T,\alpha)$, où on rappelle que $T$ est un
+symbole nonterminal et $\alpha$ un pseudo-mot (et on notera $T
+\rightarrow \alpha$, cf. ci-dessous) doivent se comprendre
+intuitivement comme « le symbole $T$ peut être remplacé
+par $\alpha$ ».  On part de l'axiome $S$, et on peut effectuer
+librement des substitutions $T \rightarrow \alpha$ (consistant à
+remplacer un nonterminal $T$ par un pseudo-mot $\alpha$) autorisées
+par les règles : le langage défini par la grammaire est l'ensemble de
+tous les mots (ne comportant plus aucun nonterminal) qu'on peut
+obtenir de la sorte.
+
+Rendons maintenant cette définition précise :
+
+\thingy Lorsque $G$ est une grammaire hors-contexte comme
+en \ref{definition-context-free-grammar}, on note $T
+\mathrel{\rightarrow_G} \alpha$, ou simplement $T \rightarrow \alpha$
+(lorsque $G$ est clair) pour signifier que $(T,\alpha)$ est une règle
+de $G$.
+
+On définit une relation $\Rightarrow$ en posant $\gamma T \gamma'
+\Rightarrow \gamma\alpha\gamma'$ pour toute règle $(T,\alpha)$ et tous
+pseudo-mots $\gamma,\gamma'$ : autrement dit, formellement, on définit
+$\lambda\Rightarrow\xi$ lorsqu'il existe $\gamma,\gamma' \in
+(\Sigma\cup N)^*$ et $(T,\alpha) \in R$ (ensemble des règles de $G$)
+tels que $\lambda = \gamma T \gamma'$ et $\xi = \gamma\alpha\gamma'$.
+Concrètement, $\lambda\Rightarrow\xi$ signifie donc que $\xi$ est
+obtenu en remplaçant un nonterminal $T$ du pseudo-mot $\lambda$ par la
+partie droite d'une production $T \rightarrow \alpha$ de la
+grammaire $G$ : on dit encore que $\lambda \Rightarrow \xi$ est une
+\textbf{dérivation immédiate} de $G$.  (On pourra dire que $T
+\rightarrow \alpha$ est la règle \textbf{appliquée} dans cette
+dérivation immédiate, et que $\gamma$ et $\gamma'$ sont respectivement
+le \textbf{contexte gauche} et le \textbf{contexte droit} de
+l'application de la règle.)  Bien sûr, si nécessaire, on précisera la
+grammaire appliquée en écrivant $\lambda \mathrel{\Rightarrow_G} \xi$
+au lieu de simplement $\lambda\Rightarrow\xi$.
+
+Une suite de pseudo-mots $(\lambda_0,\ldots,\lambda_n)$ telle que
+\[
+\lambda_0 \Rightarrow \lambda_1 \Rightarrow \cdots \Rightarrow \lambda_n
+\]
+autrement dit $\lambda_{i-1} \Rightarrow \lambda_i$ pour chaque $1\leq
+i\leq n$, est appelée \textbf{dérivation} de $\lambda_n$ à partir de
+$\lambda_0$ dans la grammaire $G$, et on note $\lambda_0
+\mathrel{\Rightarrow^*} \lambda_n$ pour indiquer son existence
+(c'est-à-dire, si on préfère, que la relation $\Rightarrow^*$ est la
+clôture réflexive-transitive de $\Rightarrow$, i.e., la plus petite
+relation binaire réflexive et transitive contenant $\Rightarrow$).
+Remarquons que $n=0$ est permis, autrement dit $\lambda
+\mathrel{\Rightarrow^*} \lambda$ pour tout pseudo-mot $\lambda$.  Bien
+sûr, si nécessaire, on précisera la grammaire appliquée en écrivant
+$\lambda \mathrel{\Rightarrow^*_G} \xi$ au lieu de simplement $\lambda
+\mathrel{\Rightarrow^*} \xi$.
+
+Concrètement, $\lambda \mathrel{\Rightarrow^*} \xi$ signifie donc
+qu'on peut passer de $\lambda$ à $\xi$ en effectuant une suite
+(finie !) de dérivations immédiates, c'est-à-dire en remplaçant à
+chaque étape un nonterminal $T$ par la partie droite $\alpha$ d'une
+règle $T \to \alpha$ de la grammaire $G$.
+
+Il va de soi qu'un pseudo-mot qui ne comporte que des terminaux, i.e.,
+qui est en fait un mot (sur $\Sigma$), ne peut pas être dérivé plus
+loin.  Ceci justifie au moins en partie la terminologie de
+« terminal ».
+
+\thingy Le \textbf{langage engendré} $L(G)$ par une grammaire
+hors-contexte $G$ est l'ensemble des mots $w$ (ne comportant plus de
+nonterminaux !) qui peuvent s'obtenir par dérivation à partir de
+l'axiome $S$ de $G$, autrement dit :
+\[
+L(G) = \{w \in \Sigma^* : S \mathrel{\Rightarrow^*} w\}
+\]
+
+Un langage qui peut s'écrire sous la forme $L(G)$ où $G$ est une
+grammaire hors-contexte est appelé \textbf{langage hors-contexte} ou
+\textbf{algébrique}.
+
+\thingy À titre d'exemple, considérons la grammaire sur l'alphabet
+$\Sigma = \{a,b\}$ donnée par
+\[
+\begin{aligned}
+S &\rightarrow aSb\\
+S &\rightarrow \varepsilon\\
+\end{aligned}
+\]
+où implicitement $S$ est l'axiome et le seul nonterminal : autrement
+dit, $G$ est donnée par $N = \{S\}$, d'axiome $S$, et de règles de
+production $(S,aSb)$ et $(S,\varepsilon)$ (où $\varepsilon$, bien
+entendu, désigne le mot vide).  Un pseudo-mot pour cette grammaire est
+un mot sur l'alphabet $\Sigma\cup N = \{a,b,S\}$, et une dérivation
+immédiate consiste \emph{soit} à ajouter un $a$ et un $b$ à gauche et
+à droite d'un $S$ dans un pseudo-mot, \emph{soit} à retirer un $S$.
+
+Dans ces conditions, il est clair qu'une dérivation partant de
+l'axiome $S$ est constituée d'un certain nombre d'applications de la
+première règle suivi d'au plus une application de la seconde (puisque
+le nombre d'occurrences de $S$ va alors tomber de $1$ à $0$ et on ne
+pourra plus dériver).  Autrement dit, une telle dérivation prend la
+forme
+\[
+S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow \cdots \Rightarrow a^n
+S b^n
+\]
+ou éventuellement
+\[
+S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow \cdots \Rightarrow a^n
+S b^n \Rightarrow a^n b^n
+\]
+Le langage $L(G)$ défini par la grammaire est donc $\{a^n b^n :
+n\in\mathbb{N}\}$.  (On a vu en \ref{example-of-pumping-lemma} que ce
+langage n'est pas rationnel : il existe donc des langages algébriques
+qui ne sont pas rationnels.)
+
+
 
 %
 %