diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 14 |
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 |