summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-02 15:07:34 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-02 15:07:34 +0100
commitfb03b072ff55ef36cd244285e46ebb51db715cec (patch)
treed2882e886f8e5b5e588fbd1020bfff1360abab59 /notes-inf105.tex
parentdc8fad6b056a901e199f94e185d02a8be7315fc7 (diff)
downloadinf105-fb03b072ff55ef36cd244285e46ebb51db715cec.tar.gz
inf105-fb03b072ff55ef36cd244285e46ebb51db715cec.tar.bz2
inf105-fb03b072ff55ef36cd244285e46ebb51db715cec.zip
Standardize spelling of "hors contexte".
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex12
1 files changed, 6 insertions, 6 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 03a19b2..d832a7e 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2888,7 +2888,7 @@ obtenir de la sorte.
Rendons maintenant cette définition précise :
-\thingy Lorsque $G$ est une grammaire hors-contexte comme
+\thingy Lorsque $G$ est une grammaire hors contexte comme
en \ref{definition-context-free-grammar}, on note $T
\mathrel{\rightarrow_G} \alpha$, ou simplement $T \rightarrow \alpha$
(lorsque $G$ est clair) pour signifier que $(T,\alpha)$ est une règle
@@ -2941,7 +2941,7 @@ loin. Ceci justifie au moins en partie la terminologie de
« terminal ».
\thingy Le \textbf{langage engendré} $L(G)$ par une grammaire
-hors-contexte $G$ est l'ensemble des mots $w$ (ne comportant plus de
+hors contexte $G$ est l'ensemble des mots $w$ (ne comportant plus de
nonterminaux !) qui peuvent s'obtenir par dérivation à partir de
l'axiome $S$ de $G$, autrement dit :
\[
@@ -2949,7 +2949,7 @@ L(G) = \{w \in \Sigma^* : S \mathrel{\Rightarrow^*} w\}
\]
Un langage qui peut s'écrire sous la forme $L(G)$ où $G$ est une
-grammaire hors-contexte est appelé \textbf{langage hors-contexte} ou
+grammaire hors contexte est appelé \textbf{langage hors contexte} ou
\textbf{algébrique}.
\thingy\label{basic-example-context-free-grammar} À titre d'exemple,
@@ -2993,7 +2993,7 @@ fait suivant :
\begin{prop}\label{rational-languages-are-algebraic}
Tout langage rationnel est algébrique. Mieux, on peut déduire
-algorithmiquement une grammaire hors-contexte $G$ d'un εNFA $A$ de
+algorithmiquement une grammaire hors contexte $G$ d'un εNFA $A$ de
façon à avoir $L(G) = L(A)$.
\end{prop}
\begin{proof}
@@ -3002,7 +3002,7 @@ généralité qu'il a un unique état initial $q_0$ (quitte à en créer un
et à remplacer tout état $q$ anciennement initial par une ε-transition
$q_0 \to q$). Soit $Q$ son ensemble des états et $\delta \subseteq Q
\times (\Sigma\cup\{\varepsilon\}) \times Q$ sa fonction de
-transition. On construit une grammaire hors-contexte $G$ dont
+transition. On construit une grammaire hors contexte $G$ dont
l'ensemble des nonterminaux est $Q$, l'axiome est $S := q_0$, (A) pour
chaque transition $(q,t,q') \in \delta$ une règle $q \to tq'$ (on
rappelle que $t \in \Sigma\cup\{\varepsilon\}$), et (B) pour chaque
@@ -3024,7 +3024,7 @@ t_n$ dérivé est précisément le mot formé en concacténant les
étiquettes du chemin. On a donc bien $L(G) = L(A)$.
\end{proof}
-\thingy Une grammaire hors-contexte telle que construite dans la
+\thingy Une grammaire hors contexte telle que construite dans la
preuve de \ref{rational-languages-are-algebraic} est dite
\textbf{régulière} : autrement dit, il s'agit d'une grammaire ayant
uniquement des règles de la forme (A) $Q \to tQ'$ où $t \in