Some remarks on degenerate cases.

1 files changed, 27 insertions, 2 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index b70fc0f..64c8504 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1710,8 +1710,15 @@ transitions qui y conduisent).
 Un DFAi dont tous les états sont à la fois accessibles et
 co-accessibles (on les dit aussi \defin[utile (état)]{utiles}) est
 parfois appelé \defin[émondé (automate)]{émondé}.  On peut émonder un
-DFAi en ne conservant que ses états utiles : ainsi, tout DFAi est
-équivalent à un DFAi émondé.
+DFAi en ne conservant que ses états utiles\footnote{Si on aime
+  pinailler, il y a un petit problème pour émonder un DFAi n'ayant
+  aucun état final (donc aucun état co-accessible, donc aucun état
+  utile) ; pour résoudre ce problème, on peut modifier légèrement la
+  définition d'un DFAi et autoriser que l'état initial ne soit pas
+  défini (auquel cas l'automate n'accepte évidemment aucun mot, i.e.,
+  reconnaît le langage $\varnothing$), si bien que l'automate émondé
+  d'un DFAi sans état final est l'automate vide (sans aucun état).} :
+ainsi, tout DFAi est équivalent à un DFAi émondé.
 
 \thingy Il faut prendre garde au fait que certains auteurs définissent
 les « automates finis déterministes » (sans précision supplémentaire)
@@ -4230,6 +4237,24 @@ En revanche, si on change l'automate pour rendre l'état $4$ non-final
 aboutit sur la partition triviale en six états, c'est-à-dire que
 l'automate est, en fait, déjà minimal.
 
+{\footnotesize\thingy\textbf{Cas dégénérés :} Si aucun état d'un DFA
+  n'est final (c'est-à-dire s'il reconnaît le langage
+  vide $\varnothing$), alors l'algorithme de minimisation termine
+  immédiatement avec une seule classe d'équivalence, et donne donc un
+  automate minimal ayant un unique état, initial mais non final, et
+  des transitions étiquetées par toutes les lettres de cet état vers
+  lui-même.  Si \emph{tous} les états d'un DFA sont finaux (il
+  reconnaît le langage $\Sigma^*$ de tous les mots), de même,
+  l'algorithme de minimisation termine immédiatement avec une seule
+  classe d'équivalence, et donne donc un automate minimal ayant un
+  unique état, à la fois initial et final (et toujours des transitions
+  étiquetées par toutes les lettres de cet état vers lui-même).\par}
+
+\bigbreak
+
+Énonçons ici le fait évoqué plus haut comme application de
+l'algorithme de minimisation :
+
 \begin{cor}\label{equivalence-of-regexps-is-decidable}
 On peut décider algorithmiquement si deux automates finis (de
 n'importe quelle sorte), ou deux expressions rationnelles, ou un