From 13b7f25d577023a02722f650813ddab99cce258a Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 25 Nov 2016 15:26:19 +0100 Subject: Example of state elimination. --- figs/example6.dot | 14 ++++++++++ figs/example6b.dot | 11 ++++++++ figs/example6c.dot | 11 ++++++++ notes-inf105.tex | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 116 insertions(+), 1 deletion(-) create mode 100644 figs/example6.dot create mode 100644 figs/example6b.dot create mode 100644 figs/example6c.dot diff --git a/figs/example6.dot b/figs/example6.dot new file mode 100644 index 0000000..9797c60 --- /dev/null +++ b/figs/example6.dot @@ -0,0 +1,14 @@ +digraph example6 { + rankdir="LR"; + node [texmode="math",shape="circle",style="state"]; + q0 [style="state,initial,final,accepting below",label="0"]; + q1 [style="state",label="1"]; + q2 [style="state",label="2"]; + edge [texmode="math",lblstyle="auto"]; + q0 -> q0 [label="0",topath="loop above"]; + q0 -> q1 [label="1"]; + q1 -> q0 [label="1"]; + q1 -> q2 [label="0"]; + q2 -> q1 [label="0"]; + q2 -> q2 [label="1",topath="loop above"]; +} diff --git a/figs/example6b.dot b/figs/example6b.dot new file mode 100644 index 0000000..8f2d77e --- /dev/null +++ b/figs/example6b.dot @@ -0,0 +1,11 @@ +digraph example6b { + rankdir="LR"; + node [texmode="math",shape="circle",style="state"]; + q0 [style="state,initial,final,accepting below",label="0"]; + q1 [style="state",label="1"]; + edge [texmode="math",lblstyle="auto"]; + q0 -> q0 [label="0",topath="loop above"]; + q0 -> q1 [label="1"]; + q1 -> q0 [label="1"]; + q1 -> q1 [label="1",topath="loop right",texlbl="$01{*}0$"]; +} diff --git a/figs/example6c.dot b/figs/example6c.dot new file mode 100644 index 0000000..64dfcb3 --- /dev/null +++ b/figs/example6c.dot @@ -0,0 +1,11 @@ +digraph example6c { + rankdir="LR"; + node [texmode="math",shape="circle",style="state"]; + q0 [style="state,initial,final,accepting below",label="0"]; + q2 [style="state",label="2"]; + edge [texmode="math",lblstyle="auto"]; + q0 -> q0 [label="0",topath="loop above",texlbl="$0|11$"]; + q0 -> q2 [label="10"]; + q2 -> q2 [label="1",topath="loop above",texlbl="$1|00$"]; + q2 -> q0 [label="01"]; +} 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