Rational languages are algebraic; regular grammars.

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.