summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-23 14:55:04 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-11-23 14:55:04 (GMT)
commit6168f9ba59dca0c5bc3c39066011d9a227a9156c (patch)
tree3e185c49bf98a551613a46879613f3ef5091febd /notes-inf105.tex
parentf6780feb6aae79f7a476547cb68b37b97bc5d585 (diff)
downloadinf105-6168f9ba59dca0c5bc3c39066011d9a227a9156c.zip
inf105-6168f9ba59dca0c5bc3c39066011d9a227a9156c.tar.gz
inf105-6168f9ba59dca0c5bc3c39066011d9a227a9156c.tar.bz2
Trimming of incomplete DFAs.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex39
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é.
+
%
%