From 5680275cc29bd25cecb65ae5c3ce94601e9a6384 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 3 Jan 2017 13:25:21 +0100
Subject: Briefly mention more general grammars.  Start writing about
 ambiguity.

---
 notes-inf105.tex | 31 ++++++++++++++++++++++++++++---
 1 file changed, 28 insertions(+), 3 deletions(-)

diff --git a/notes-inf105.tex b/notes-inf105.tex
index ea10ff6..9f36e62 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2840,9 +2840,9 @@ et les langages reconnus sont les mêmes.
 \subsection{Définition, notations et premier exemple}
 
 \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
+  hors contexte} (on dit parfois aussi « sans contexte » ; en
+anglais, « context-free grammar » ou « CFG » ; ou encore grammaire de
+\textbf{type 2}) sur un alphabet $\Sigma$ est la donnée
 \begin{itemize}
 \item d'un second alphabet $N$, disjoint de $\Sigma$, appelé ensemble
   des \textbf{nonterminaux},
@@ -2997,6 +2997,19 @@ rationnel : il existe donc des langages algébriques qui ne sont pas
 rationnels.  En revanche, pour ce qui est de la réciproque, on verra
 dans la section suivante que tout langage rationnel est algébrique.
 
+\thingy Mentionnons brièvement qu'il existe des types de grammaires
+plus généraux que les grammaires hors contexte.  Les
+\textbf{grammaires contextuelles} (ou grammaires de \textbf{type 1})
+sont définies par des règles du type $\gamma T \gamma' \rightarrow
+\gamma \alpha \gamma'$ où $T$ est un nonterminal, et
+$\alpha,\gamma,\gamma'$ des pseudo-mots (=mots sur l'alphabet de tous
+les symboles), c'est-à-dire des règles qui autorisent la réécriture
+d'un symbole $T$ en $\alpha$ mais uniquement s'il est entouré d'un
+certain contexte ($\gamma$ à gauche, $\gamma'$ à droite).  Les
+\textbf{grammaires syntagmatiques générales} (ou grammaires de
+\textbf{type 0}) sont définies par des règles de réécriture $\lambda
+\rightarrow \mu$ où $\lambda,\mu$ sont des pseudo-mots quelconques.
+
 
 \subsection{Langages rationnels et algébriques, stabilité}
 
@@ -3486,6 +3499,18 @@ n'est pas une feuille.  De même, à chaque arbre d'analyse est associée
 une et une seule dérivation droite.
 
 
+\subsection{Ambiguïté}
+
+\thingy On dit qu'une grammaire hors contexte est \textbf{ambiguë}
+lorsqu'il existe un mot (i.e., un mot sur l'alphabet $\Sigma$ des
+terminaux) qui admet deux arbres d'analyse \emph{différents}.  Dans le
+cas contraire, elle est dite \textbf{inambiguë} : autrement dit, une
+grammaire inambiguë est une grammaire $G$ pour laquelle tout $w \in
+L(G)$ a un unique arbre d'analyse ; il revient au même de dire que
+tout mot de $L(G)$ a une unique dérivation droite, ou encore que tout
+mot de $L(G)$ a une unique dérivation gauche.
+
+
 %
 %
 %
-- 
cgit v1.2.3