From 13b7f25d577023a02722f650813ddab99cce258a Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 25 Nov 2016 15:26:19 +0100
Subject: Example of state elimination.

---
 notes-inf105.tex | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 80 insertions(+), 1 deletion(-)

(limited to 'notes-inf105.tex')

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 11a081c..925301a 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2013,7 +2013,10 @@ l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).
 En supprimant (dans n'importe quel ordre) tous les états autres que
 $q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique
 transition $(q_0,r,q_\infty)$, qui est donc essentiellement
-l'expression rationnelle $r$.
+l'expression rationnelle $r$ (si $q_\infty$ et $q_0$ ne sont pas
+distincts, on peut ajouter un nouvel état initial, un nouvel état
+final, et éliminer l'état commun :
+cf. l'exemple \ref{example-of-state-elimination}).
 \end{proof}
 
 \thingy La procédure qu'on a décrite dans la démonstration de cette
@@ -2033,6 +2036,82 @@ traiter aussi.
 En général, l'élimination des états conduit à un expression
 extrêmement compliquée.
 
+\thingy\label{example-of-state-elimination} À titre d'exemple,
+considérons le DFA suivant sur l'alphabet $\{0,1\}$, qui reconnaît les
+suites binaires qui représentent un nombre multiple de $3$ écrit en
+binaire (en convenant que le mot vide est une représentation binaire
+du nombre $0$, ce qui est logique) :
+
+\begin{center}
+%%% begin example6 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
+  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$1$} (q0);
+  \draw [->] (q2) to[loop above] node[auto] {$1$} (q2);
+  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$0$} (q1);
+  \draw [->] (q0) to[loop above] node[auto] {$0$} (q0);
+  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$1$} (q1);
+  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$0$} (q2);
+%
+\end{tikzpicture}
+
+%%% end example6 %%%
+\end{center}
+
+L'élimination de l'état $2$ conduit à l'automate suivant :
+
+\begin{center}
+%%% begin example6b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$1$} (q0);
+  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$1$} (q1);
+  \draw [->] (q1) to[loop right] node[auto] {$01{*}0$} (q1);
+  \draw [->] (q0) to[loop above] node[auto] {$0$} (q0);
+%
+\end{tikzpicture}
+
+%%% end example6b %%%
+\end{center}
+
+Et l'élimination de l'état $1$ conduit alors à l'automate ayant un
+unique état $0$, à la fois initial et final, avec une transition vers
+lui-même étiquetée $0|1(01{*}0){*}1$.  Tel quel, cet automate n'est
+pas sous la forme d'une expression rationnelle parce que l'état
+initial et l'état final ne sont pas distincts, mais on peut bien sûr
+les séparer, et on obtient l'expression rationnelle
+$(0|1(01{*}0){*}1){*}$.
+
+On pouvait aussi choisir d'éliminer l'état $1$ en premier, ce qui
+conduit à l'automate suivant :
+
+\begin{center}
+%%% begin example6c %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,20.114bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \node (q2) at (104bp,20.114bp) [draw,circle,state] {$2$};
+  \draw [->] (q2) ..controls (82.598bp,6.6202bp) and (75.237bp,2.9515bp)  .. (68bp,1.1137bp) .. controls (59.228bp,-1.1137bp) and (49.898bp,1.2372bp)  .. node[auto] {$01$} (q0);
+  \draw [->] (q0) ..controls (47.743bp,20.114bp) and (62.773bp,20.114bp)  .. node[auto] {$10$} (q2);
+  \draw [->] (q0) to[loop above] node[auto] {$0|11$} (q0);
+  \draw [->] (q2) to[loop above] node[auto] {$1|00$} (q2);
+%
+\end{tikzpicture}
+
+%%% end example6c %%%
+\end{center}
+
+\noindent et finalement à l'expression rationnelle
+$(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente.
+
 
 %
 %
-- 
cgit v1.2.3