summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-02 13:37:14 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-02 13:37:14 +0100
commitdc8fad6b056a901e199f94e185d02a8be7315fc7 (patch)
tree2a213e924b52592ed70ca2b5f98c3d4472d5162c /notes-inf105.tex
parent5ade028a9eabd597e8e924230626833c82d806f0 (diff)
downloadinf105-dc8fad6b056a901e199f94e185d02a8be7315fc7.zip
inf105-dc8fad6b056a901e199f94e185d02a8be7315fc7.tar.gz
inf105-dc8fad6b056a901e199f94e185d02a8be7315fc7.tar.bz2
Rational languages are algebraic; regular grammars.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex61
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.