diff options
| -rw-r--r-- | notes-inf105.tex | 39 |
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é. + % % |