diff options
| -rw-r--r-- | notes-inf105.tex | 12 |
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 |