From 79e653484b265344c00af7e708c1b7c521e719d8 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 27 Oct 2017 21:21:05 +0200
Subject: Glushkov automata: define properly.
---
notes-inf105.tex | 63 ++++++++++++++++++++++++++++++++++++++++++++++----------
1 file changed, 52 insertions(+), 11 deletions(-)
diff --git a/notes-inf105.tex b/notes-inf105.tex
index efb4a57..6312c88 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2084,7 +2084,7 @@ choix.
\section{Langages reconnaissables et langages rationnels}\label{section-recognizable-languages}
-\subsection{Stabilité des langages reconnaissables}
+\subsection{Stabilité des langages reconnaissables par opérations booléennes et miroir}
\thingy On rappelle qu'on a défini un langage \index{reconnaissable
(langage)}reconnaissable comme un langage $L$ pour lequel il existe
@@ -2213,12 +2213,15 @@ chaque état $q$ et chaque lettre $x$, il existe une unique arête
aboutissant à $q$ et étiquetée par $x$ — sont parfois dits
« co-déterministes ».)
+\subsection{Stabilité des langages reconnaissables par opérations rationnelles, automates standards}
+
\thingy Nous allons maintenant montrer que la classe des langages
reconnaissables est stable par les opérations rationnelles (union,
concaténation et étoile de Kleene,
-cf. \ref{stable-under-rational-operations} ; on l'a déjà vu pour la
-réunion, mais on va en donner une nouvelle démonstration, qui a un
-contenu algorithmique utile dans des circonstances différentes).
+cf. \ref{stable-under-rational-operations} ; on l'a déjà vu sur les
+DFA en \ref{dfa-union-and-intersection} pour la réunion, mais on va en
+donner une nouvelle démonstration, cette fois basée sur les NFA, qui a
+un contenu algorithmique utile dans des circonstances différentes).
Pour établir ces stabilités, on va travailler sur les NFA et utiliser
la construction parfois appelée « de Glushkov » ou « automate
@@ -2567,6 +2570,29 @@ final dans cet automate $A'$ consiste en un nombre quelconque
dans $A$. On a donc bien $L_{A'} = L^*$.
\end{proof}
+\thingy\label{trivial-standard-automata} Il sera utile de fixer
+également des NFA (« standards » au sens de
+\ref{standard-automaton-lemma}) reconnaissant les langages de base
+triviaux $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour
+chaque $x\in\Sigma$). On prendra les suivants :
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$};
+\end{tikzpicture}
+pour le langage $\varnothing$\\
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final] {$q_0$};
+\end{tikzpicture}
+pour le langage $\{\varepsilon\}$\\
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,final] {$q_1$};
+\draw [->] (q0) to node[auto,swap] {$x$} (q1);
+\end{tikzpicture}
+pour le langage $\{x\}$.
+\end{center}
+
\begin{cor}\label{rational-languages-are-recognizable}
Tout langage rationnel est reconnaissable ; de plus, un NFA le
reconnaissant se déduit algorithmiquement d'une expression rationnelle
@@ -2577,9 +2603,9 @@ algorithmiquement si un mot vérifie une expression rationnelle.)
Cela résulte de façon évidente de la définition des langages
rationnels (cf. §\ref{subsection-rational-languages}), du fait que les
langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour
-chaque $x\in\Sigma$) sont reconnaissables par automates finis, et des
-propositions \ref{nfa-union}, \ref{nfa-concatenation}
-et \ref{nfa-star}.
+chaque $x\in\Sigma$) sont reconnaissables par automates finis
+(cf. \ref{trivial-standard-automata}), et grâce aux propositions
+\ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}.
Pour décider si un mot vérifie une expression rationnelle, on peut
commencer par transformer cette expression rationnelle en NFA standard
@@ -2590,10 +2616,25 @@ automate en DFA quitte déterminiser
si l'automate accepte le mot.
\end{proof}
-\textcolor{red}{TODO: Standardiser la construction des automates. Par
- exemple, utiliser le NFA « standard » ou « de Glushkov » (ayant un
- seul état initial, éventuellement final, sans aucune transition qui
- y mène).}
+\thingy Les constructions que nous avons décrites dans cette section
+associent naturellement un NFA standard à chaque expression
+rationnelle : il s'obtient en partant des automates décrits
+en \ref{trivial-standard-automata} et en appliquant les constructions
+décrites dans les démonstrations de \ref{nfa-union},
+\ref{nfa-concatenation} et \ref{nfa-star}. Cette automate standard,
+parfois appelé automate « de Glushkov », possède les propriétés
+suivantes :
+\begin{itemize}
+\item c'est un NFA reconnaissant le langage $L_r$ dénoté par
+ l'expression rationnelle $r$ dont on est parti,
+\item il est standard au sens de \ref{standard-automaton-lemma},
+ c'est-à-dire qu'il possède un unique état initial qui n'est la cible
+ d'aucune transition,
+\item son nombre d'états est égal à $1$ plus le nombre de lettres (à
+ l'exclusion des métacaractères) contenues dans l'expression $r$.
+\end{itemize}
+
+\textcolor{red}{TODO: Développer, et donner des exemples.}
\subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)}
--
cgit v1.2.3