diff options
| -rw-r--r-- | notes-inf105.tex | 29 |
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 |