summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-03 12:25:21 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-03 12:25:21 (GMT)
commit5680275cc29bd25cecb65ae5c3ce94601e9a6384 (patch)
treec9707c60708c828bdc60fd5e113d8b8361f36a82 /notes-inf105.tex
parent918d8bbe0b7bcadf43ae0cc9881c0f55c9ad52de (diff)
downloadinf105-5680275cc29bd25cecb65ae5c3ce94601e9a6384.zip
inf105-5680275cc29bd25cecb65ae5c3ce94601e9a6384.tar.gz
inf105-5680275cc29bd25cecb65ae5c3ce94601e9a6384.tar.bz2
Briefly mention more general grammars. Start writing about ambiguity.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex31
1 files 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.
+
+
%
%
%