diff options
| -rw-r--r-- | notes-inf105.tex | 36 |
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} + + % % |