diff options
| -rw-r--r-- | notes-inf105.tex | 61 |
1 files changed, 55 insertions, 6 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index c8b4703..03a19b2 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2870,7 +2870,9 @@ ne comportant que des symboles terminaux). Typographiquement, on aura tendance à utiliser des lettres minuscules pour désigner les symboles terminaux, et majuscules pour désigner les symboles nonterminaux ; et on aura tendance à utiliser des lettres -grecques minuscules pour désigner les pseudo-mots. +grecques minuscules pour désigner les pseudo-mots. (Mais il n'est pas +possible de suivre cette convention de façon complètement +systématique.) \thingy Intuitivement, il faut comprendre la grammaire de la manière suivante. Les règles $(T,\alpha)$, où on rappelle que $T$ est un @@ -2950,8 +2952,8 @@ 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 \textbf{algébrique}. -\thingy À titre d'exemple, considérons la grammaire sur l'alphabet -$\Sigma = \{a,b\}$ donnée par +\thingy\label{basic-example-context-free-grammar} À titre d'exemple, +considérons la grammaire sur l'alphabet $\Sigma = \{a,b\}$ donnée par \[ \begin{aligned} S &\rightarrow aSb\\ @@ -2982,9 +2984,56 @@ S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow \cdots \Rightarrow a^n S b^n \Rightarrow a^n b^n \] Le langage $L(G)$ défini par la grammaire est donc $\{a^n b^n : -n\in\mathbb{N}\}$. (On a vu en \ref{example-of-pumping-lemma} que ce -langage n'est pas rationnel : il existe donc des langages algébriques -qui ne sont pas rationnels.) +n\in\mathbb{N}\}$. + +On a vu en \ref{example-of-pumping-lemma} que ce langage n'est pas +rationnel : il existe donc des langages algébriques qui ne sont pas +rationnels. En revanche, pour ce qui est de la réciproque, on a le +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 +façon à avoir $L(G) = L(A)$. +\end{prop} +\begin{proof} +Soit $A$ un εNFA : on sait qu'on peut supposer sans perte de +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 +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 +état final $q\in F$ une règle $q\to\varepsilon$. + +De même que dans l'exemple \ref{basic-example-context-free-grammar}, +une dérivation partant de l'axiome va comporter un certain nombre +d'applications de règles de type (A) suivies éventuellement d'une +unique application d'une règle de type (B) (ce qui est nécessaire pour +faire passer le nombre de nonterminaux de $1$ à $0$). Autrement dit, +elle prend la forme $q_0 \Rightarrow t_1 q_1 \Rightarrow t_1 t_2 q_2 +\Rightarrow \cdots \Rightarrow t_1 t_2\cdots t_n q_n$ où +$(q_{i-1},t_i,q_i) \in \delta$ pour $1\leq i\leq n$, suivie +éventuellement par $t_1\cdots t_n q_n \Rightarrow t_1\cdots t_n$ +lorsque $q_n \in F$. Manifestement, les dérivations de la sorte +(terminant sur un mot sur $\Sigma$) sont en bijection avec les chemins +$q_0 \to \cdots \to q_n$ dans $A$ où $q_n \in F$, et le mot $t_1\cdots +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 +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 +\Sigma\cup\{\varepsilon\}$ (certains auteurs imposent $t \in \Sigma$, +ce qui revient à imposer qu'on part d'un NFA sans ε-transition dans la +construction) et (B) $Q \to \varepsilon$ (certains auteurs préfèrent +$Q \to x$ avec $x\in\Sigma$, ce qui impose des petits changements dans +la construction ci-dessus). Les langages définis par des grammaires +régulières sont donc exactement les langages rationnels. |