Minor clarifications on formal grammars.

1 files changed, 11 insertions, 3 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 64c8504..1f21b04 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -4564,7 +4564,11 @@ entouré d'un certain contexte ($\gamma$ à gauche, $\gamma'$ à droite).
 Les \defin[grammaire syntagmatique]{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.
+des pseudo-mots quelconques, c'est-à-dire qu'elles permettent la
+réécriture de multiples symboles à la fois.  Dans tous les cas, le
+langage défini par la grammaire est l'ensemble de tous les mots (sans
+nonterminaux) qui peuvent s'obtenir par application des règles de
+remplacement à partir de l'axiome.
 
 
 \subsection{Langages rationnels et algébriques, stabilité}
@@ -4677,6 +4681,7 @@ peut s'écrire $S \rightarrow aSb | \varepsilon$.  Il s'agit d'un
 simple racourci d'écriture (comparer avec une convention semblable
 faite pour les automates en \ref{graphical-representation-of-dfa}).
 
+{\footnotesize
 On pourrait même se permettre l'abus de notation consistant à écrire
 $T \rightarrow U^*$ pour $T \rightarrow UT|\varepsilon$ (c'est-à-dire
 $T \rightarrow UT$ et $T \rightarrow \varepsilon$), mais il vaut mieux
@@ -4693,6 +4698,7 @@ nonterminaux pour les expressions intermédiaires (par exemple, $T
 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.
+\par}
 
 \thingy Il peut être utile, pour raisonner sur les langages
 algébriques, d'introduire, lorsque $G$ est une grammaire hors contexte
@@ -4711,6 +4717,8 @@ d'équations portant sur des langages (par exemple, la grammaire de
 définition des grammaires hors contexte revient à considérer la plus
 petite (au sens de l'inclusion) solution de ce système d'équations.
 
+\bigbreak
+
 \thingy À la différence des langages rationnels, il \emph{n'est pas
   vrai} en général que l'intersection de deux langages algébriques
 soit algébrique : un contre-exemple est fourni par les deux langages
@@ -5107,8 +5115,8 @@ mot de $L(G)$ a une unique dérivation gauche.
 Les grammaires des langages informatiques réels sont évidemment
 (presque ?) toujours inambiguës : on souhaite qu'un programme
 (c'est-à-dire, dans la terminologie mathématique, un mot du langage)
-admette une unique interprétation, une unique analyse, autrement dit,
-un unique arbre d'analyse.
+admette une unique interprétation, autrement dit, un unique arbre
+d'analyse.
 
 \thingy\label{trivial-example-ambiguity} À titre d'exemple, la
 grammaire