Trimming of incomplete DFAs.

1 files changed, 31 insertions, 8 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index ded4af0..90a0889 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -847,14 +847,17 @@ sous-mot (cf. \ref{definition-subword}).  Ce langage est donc
 reconnaissable.  (Il est aussi rationnel puisque désigné par
 l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.)
 
-\thingy Un état $q$ d'un DFA $A$ est dit \textbf{accessible} lorsqu'il
-existe un mot $w \in \Sigma^*$ tel que $q = \delta(q_0,w)$, autrement
-dit, graphiquement, lorsqu'il existe un chemin orienté
-$q_0,q_1,\ldots,q_n=q$ reliant l'état initial $q_0$ à l'état $q$
-considéré.  Dans le cas contraire, il est dit \textbf{inaccessible}.
-Il est évident qu'ajouter ou retirer (ou modifier) les états
-inaccessibles dans un DFA ne change rien au langage reconnu au sens
-où on obtient des langages équivalents.
+\thingy\label{definition-dfa-accessible-state} Un état $q$ d'un DFA
+est dit \textbf{accessible} lorsqu'il existe un mot $w \in \Sigma^*$
+tel que $q = \delta(q_0,w)$, autrement dit, graphiquement, lorsqu'il
+existe un chemin orienté $q_0,q_1,\ldots,q_n=q$ reliant l'état
+initial $q_0$ à l'état $q$ considéré : bref, cela correspond à un état
+auquel il est possible que l'automate arrive (en partant de l'état
+initial et en consommant un certain mot).  Dans le cas contraire,
+l'état est dit \textbf{inaccessible}.  Il est évident qu'ajouter ou
+supprimer (ou modifier) les états inaccessibles dans un DFA ne change
+rien au langage reconnu au sens où on obtient des langages
+équivalents.
 
 Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible
 (l'automate est donc équivalent à celui représenté
@@ -1051,6 +1054,26 @@ DFAI représenté en \ref{discussion-example2b} :
 %%% end example2c %%%
 \end{center}
 
+\thingy On définit un état accessible d'un DFAI comme pour un DFA
+(cf. \ref{definition-dfa-accessible-state}).
+
+On dira en outre d'un état $q$ d'un DFAI qu'il est
+\textbf{co-accessible} lorsqu'il existe un mot $w \in \Sigma^*$ tel
+que $\delta(q,w)$ soit défini et soit final, autrement dit,
+graphiquement, lorsqu'il existe un chemin orienté reliant l'état $q$
+considéré à un état final (remarquer que les états finaux eux-mêmes
+sont co-accessibles : prendre $w=\varepsilon$ dans ce qu'on vient de
+dire).  Un état non co-accessible est donc un état à partir duquel il
+est impossible de faire accepter le mot.  Cette définition pourrait
+également être faite pour les DFA, mais pour les DFAI elle présente
+l'intérêt qu'on peut supprimer les états non co-accessibles dans un
+DFAI (ainsi, bien sûr, que toutes les transitions qui y conduisent).
+
+Un DFAI dont tous les états sont à la fois accessibles et
+co-accessibles (on les dit aussi \textbf{utiles}) est parfois appelé
+\textbf{émondé}.  On peut émonder un DFAI en ne conservant que ses
+états utiles : ainsi, tout DFAI est équivalent à un DFAI émondé.
+
 
 %
 %