summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-01 18:36:20 +0100
committerDavid A. Madore <david+git@madore.org>2017-11-01 18:40:27 +0100
commitf1a6c7ecf93de4c987c4d7f43601d99026ee9e5f (patch)
treea584e94c51ca43fc2383253ba7405b748dd6f848
parent3bbc3add8dfb553054af7a1aecc8daf05f70afd3 (diff)
downloadinf105-f1a6c7ecf93de4c987c4d7f43601d99026ee9e5f.tar.gz
inf105-f1a6c7ecf93de4c987c4d7f43601d99026ee9e5f.tar.bz2
inf105-f1a6c7ecf93de4c987c4d7f43601d99026ee9e5f.zip
Minor clarifications on formal grammars.
-rw-r--r--notes-inf105.tex14
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