summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-01 15:42:40 +0100
committerDavid A. Madore <david+git@madore.org>2016-12-01 15:42:40 +0100
commit069896a82c38c6660f0d55c012c4c2796a52cdb2 (patch)
tree7135b1e9c329016c579a1582cda8a2fd8fd3ca0e /notes-inf105.tex
parent27971c9ffc49a6ca6b227ac445d463549e06ad7a (diff)
downloadinf105-069896a82c38c6660f0d55c012c4c2796a52cdb2.zip
inf105-069896a82c38c6660f0d55c012c4c2796a52cdb2.tar.gz
inf105-069896a82c38c6660f0d55c012c4c2796a52cdb2.tar.bz2
Moore's algorithm (further description).
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex36
1 files changed, 33 insertions, 3 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index e027205..7c10b3f 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2396,8 +2396,8 @@ Soit $L$ un langage. Pour $w\in \Sigma^*$, notons $w^{-1} L := \{t
\in \Sigma^* : wt \in L\}$ (autrement dit, l'ensemble des mots qu'on
peut concaténer à $w$ pour obtenir un mot de $L$). Considérons la
relation d'équivalence $\equiv$ sur $\Sigma^*$ définie par $u \equiv
-v$ si et seulement si $u^{-1}L = v^{-1}L$ (ce qui signifie, si on
-préfère, que $\forall t\in \Sigma^*\,((ut\in L) \liff (vt \in L))$).
+v$ si et seulement si $u^{-1}L = v^{-1}L$ ; ce qui signifie, si on
+préfère, que $\forall t\in \Sigma^*\,((ut\in L) \liff (vt \in L))$.
Alors :
\begin{itemize}
@@ -2484,7 +2484,7 @@ partir d'une relation d'équivalence, mais cette démonstration n'est
pas algorithmique : on va voir comment on peut le construire de fącon
algorithmique à partir d'un DFA quelconque qui reconnaît $L$.
-\begin{prop}
+\begin{prop}\label{dfa-minimization}
Soit $B = (Q_B, q_{0,B}, F_B, \delta_B)$ un DFA (complet !)
reconnaissant un langage $L$, et dont tous les états sont accessibles
(cf. \ref{definition-dfa-accessible-state}). Alors l'automate
@@ -2561,6 +2561,36 @@ cas la dernière relation calculée est la relation recherchée $(\equiv)
chaque classe d'équivalence pour $\equiv$.
\end{proof}
+\thingy L'algorithme décrit par la proposition \ref{dfa-minimization}
+porte le nom d'algorithme \textbf{de Moore} ou \textbf{de
+ minimisation} ou \textbf{de réduction}. Voici comment on peut le
+mettre en œuvre de façon plus concrète :
+\begin{itemize}
+\item s'assurer qu'on a affaire à un DFA \underline{\emph{complet sans
+ état inaccessible}} (si nécessaire, déterminiser l'automate s'il
+ n'est pas déterministe, le compléter s'il est incomplet, et
+ supprimer les états inaccessibles s'il y en a) ;
+\item appeler $\Pi$ la partition des automates en deux classes : les
+ états finaux d'un côté, et les non-finaux de l'autre ;
+\item répéter l'opération suivante tant que la partition $\Pi$
+ change : pour chaque classe $C$ de $\Pi$ et chaque lettre $x \in
+ \Sigma$, s'il existe deux états $q,q' \in C$ tels que $\delta(q,x)$
+ et $\delta(q',x)$ ne tombent pas dans la même classe de $\Pi$,
+ séparer cette classe $C$ selon la classe de $\delta(\tiret,x)$
+ (autrement dit, $q,q'$ restent dans la même classe pour la nouvelle
+ partition lorsqu'ils sont dans la même classe pour l'ancienne et que
+ pour chaque lettre $x$ leurs images $\delta(q,x)$ et $\delta(q',x)$
+ sont aussi dans la même classe) ;
+\item si $\Pi$ est la (dernière) partition ainsi obtenue, l'ensemble
+ des états de l'automate construit est l'ensemble des classes
+ de $\Pi$, les états finaux sont les classes qui contiennent un état
+ final (ils sont alors forcément tous finaux), et la fonction de
+ transition est obtenue en prenant la fonction de transition sur un
+ représentant quelconque de la classe (la classe ne doit pas dépendre
+ du représentant).
+\end{itemize}
+
+
%
%