summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-23 13:13:03 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-11-23 13:13:03 (GMT)
commit83a2cb4675358bbc4df0b50dbf25d8c295330da7 (patch)
tree4538a62aa845e7ca65f16e8e247c288e6a5c48b7 /notes-inf105.tex
parent5ee05bead1390be4a4824e06a5d52eacb15e57f1 (diff)
downloadinf105-83a2cb4675358bbc4df0b50dbf25d8c295330da7.zip
inf105-83a2cb4675358bbc4df0b50dbf25d8c295330da7.tar.gz
inf105-83a2cb4675358bbc4df0b50dbf25d8c295330da7.tar.bz2
Accessible and inaccessible states.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex71
1 files changed, 60 insertions, 11 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 76e2189..a8572db 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -699,9 +699,9 @@ consommer.
\subsection{Automates finis déterministes (=DFA)}
-\thingy Un \textbf{automate fini déterministe}, ou en abrégé
-\textbf{DFA} (pour \textit{deterministic finite automaton}) sur un
-alphabet $\Sigma$ est la donnée
+\thingy\label{definition-dfa} Un \textbf{automate fini déterministe},
+ou en abrégé \textbf{DFA} (pour \textit{deterministic finite
+ automaton}), sur un alphabet $\Sigma$ est la donnée
\begin{itemize}
\item d'un ensemble fini $Q$ dont les éléments sont appelés
\textbf{états},
@@ -731,12 +731,13 @@ $\delta(q,x) = q'$ et $\delta(q,y) = q'$), on pourra écrire « $x,y$ »
ou « $x|y$ » sur l'arête en question (et ne la tracer qu'une seule
fois). Voir \ref{discussion-example2} ci-dessous pour un exemple.
-\thingy Pour donner un exemple simple, l'automate sur $\Sigma =
-\{a,b\}$ représenté ci-dessous a $Q = \{0,1\}$ et $q_0 = 0$ et $F =
-\{1\}$ et la fonction de transition $\delta$ donnée par $\delta(0,a) =
-0$ et $\delta(0,b) = 1$ et $\delta(1,a) = 1$ et $\delta(1,b) = 0$. On
-pourra se convaincre (une fois lues les définitions plus loin) que cet
-automate accepte les mots dont le nombre de $b$ est pair.
+\thingy\label{discussion-example1} Pour donner un exemple simple,
+l'automate sur $\Sigma = \{a,b\}$ représenté ci-dessous a $Q =
+\{0,1\}$ et $q_0 = 0$ et $F = \{1\}$ et la fonction de transition
+$\delta$ donnée par $\delta(0,a) = 0$ et $\delta(0,b) = 1$ et
+$\delta(1,a) = 1$ et $\delta(1,b) = 0$. On pourra se convaincre (une
+fois lues les définitions plus loin) que cet automate accepte les mots
+dont le nombre de $b$ est pair.
\begin{center}
%%% begin example1 %%%
@@ -794,8 +795,9 @@ avec la convention faite en \ref{convention-on-words-of-length-one},
on peut dire que $\delta^*$ prolonge $\delta$).
Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$
-\textbf{accepte} un mot $w$ lorsque $\delta^*(q_0,w) =: q_n \in F$ ;
-dans le cas contraire, on dira qu'il \textbf{rejette} le mot $w$.
+\textbf{accepte} ou \textbf{reconnaît} un mot $w$ lorsque
+$\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il
+\textbf{rejette} le mot $w$.
L'ensemble $L_A$ des mots acceptés par l'automate $A$ s'appelle
\textbf{langage accepté}, ou \textbf{reconnu}, ou \textbf{défini}, par
@@ -806,6 +808,9 @@ forme du langage $L_A$ accepté par un DFA $A$ s'appelle
\textbf{reconnaissable} (sous-entendu : par automate déterministe
fini).
+On dit que deux DFA $A,A'$ sont \textbf{équivalents} lorsqu'ils
+reconnaissent le même langage, i.e., $L_A = L_{A'}$.
+
\thingy\label{discussion-example2} L'automate fini ci-dessous sur
$\Sigma := \{a,b,c\}$ a trois états, $Q = \{0,1,2\}$. On peut en
faire la description informelle suivante : l'automate commence dans
@@ -839,6 +844,50 @@ immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un
sous-mot (cf. \ref{definition-subword}). Ce langage est donc
reconnaissable.
+\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.
+
+Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible
+(l'automate est donc équivalent à celui représenté
+en \ref{discussion-example1}). On remarquera qu'il ne change rien que
+cet état soit final ou non.
+
+\begin{center}
+%%% begin example1b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (98bp,20.306bp) [draw,circle,state,final] {$1$};
+ \node (q0) at (18bp,20.306bp) [draw,circle,state,initial] {$0$};
+ \node (q2) at (172bp,20.306bp) [draw,circle,state,final] {$2$};
+ \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp) .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp) .. node[auto] {$b$} (q0);
+ \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp) .. node[auto] {$b$} (q1);
+ \draw [->] (q1) ..controls (90.319bp,47.164bp) and (92.445bp,56.306bp) .. (98bp,56.306bp) .. controls (101.47bp,56.306bp) and (103.6bp,52.735bp) .. node[auto] {$a$} (q1);
+ \draw [->] (q0) ..controls (9.4062bp,46.931bp) and (11.75bp,56.306bp) .. (18bp,56.306bp) .. controls (22.004bp,56.306bp) and (24.405bp,52.458bp) .. node[auto] {$a$} (q0);
+%
+\end{tikzpicture}
+
+%%% end example1b %%%
+\end{center}
+
+\thingy On va maintenant introduire différentes variations sur le
+thème des automates finis, c'est-à-dire différentes généralisations de
+la définition faite en \ref{definition-dfa} correspondant à des types
+d'automates finis plus puissants que les DFA mais dont on va montrer,
+à chaque fois, qu'ils peuvent se ramener à des DFA au sens où pour
+chacun de ces automates généralisés on pourra construire
+algorithmiquement un DFA qui reconnaît le même langage (si bien que la
+classe des langages reconnaissables par n'importe laquelle de ces
+sortes d'automates sera toujours la même). Les plus simples sont les
+automates déterministes finis incomplets et on va donc commencer par
+eux.
+
%
%