summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-11-01 18:25:55 +0100
committerDavid A. Madore <david+git@madore.org>2017-11-01 18:25:55 +0100
commit3bbc3add8dfb553054af7a1aecc8daf05f70afd3 (patch)
tree161087dc7f0e3d8c70743482dafde882e12701fd
parent2b1a0ea899c9d7d08c0a48f8a663ccd4660f0250 (diff)
downloadinf105-3bbc3add8dfb553054af7a1aecc8daf05f70afd3.tar.gz
inf105-3bbc3add8dfb553054af7a1aecc8daf05f70afd3.tar.bz2
inf105-3bbc3add8dfb553054af7a1aecc8daf05f70afd3.zip
Some remarks on degenerate cases.
-rw-r--r--notes-inf105.tex29
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