summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-30 17:55:20 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-30 17:55:20 +0100
commit724a5e10fd98080f49709ec5081fe1ff41c73625 (patch)
tree23f92adb65aeaa7416cdfa9205d31eb7fcf46045
parent5bfe437e9e7087fc3ddaf2cbdf49cbef51fe9b31 (diff)
downloadinf105-724a5e10fd98080f49709ec5081fe1ff41c73625.tar.gz
inf105-724a5e10fd98080f49709ec5081fe1ff41c73625.tar.bz2
inf105-724a5e10fd98080f49709ec5081fe1ff41c73625.zip
Fix mistake in minimization of automaton.
-rw-r--r--exercices1.tex50
-rw-r--r--figs/ex1p2c.dot8
2 files changed, 30 insertions, 28 deletions
diff --git a/exercices1.tex b/exercices1.tex
index d51e3b7..60fef33 100644
--- a/exercices1.tex
+++ b/exercices1.tex
@@ -357,33 +357,33 @@ construisant de proche en proche, on obtient le DFA suivant :
\definecolor{fillcol}{rgb}{1.0,1.0,1.0};
\pgfsetfillcolor{fillcol}
\end{scope}
- \node (q0) at (18bp,120.98bp) [draw,circle,state,initial] {$0$};
- \node (q027) at (382bp,28.975bp) [draw,circle,state,final] {$027$};
- \node (q056) at (188bp,57.975bp) [draw,circle,state,final,accepting below] {$056$};
- \node (q023) at (188bp,165.98bp) [draw,circle,state,final,accepting above] {$023$};
- \node (q057) at (382bp,203.98bp) [draw,circle,state,final] {$057$};
- \node (q0567) at (285bp,57.975bp) [draw,circle,state,final,accepting above] {$0567$};
- \node (q02) at (100bp,159.98bp) [draw,circle,state] {$02$};
- \node (q0237) at (285bp,165.98bp) [draw,circle,state,final,accepting below] {$0237$};
- \node (q05) at (100bp,67.975bp) [draw,circle,state] {$05$};
- \draw [->] (q057) ..controls (359.08bp,178.5bp) and (349.99bp,170.92bp) .. (340bp,166.98bp) .. controls (334.88bp,164.95bp) and (329.26bp,163.8bp) .. node[auto] {$a$} (q0237);
- \draw [->] (q027) ..controls (382bp,83.608bp) and (382bp,135.55bp) .. node[auto] {$b$} (q057);
- \draw [->] (q0) ..controls (45.352bp,133.82bp) and (60.273bp,141.1bp) .. node[auto] {$a$} (q02);
+ \node (q0) at (18bp,121.73bp) [draw,circle,state,initial] {$0$};
+ \node (q027) at (382bp,39.732bp) [draw,circle,state,final] {$027$};
+ \node (q056) at (188bp,58.732bp) [draw,circle,state,final,accepting below] {$056$};
+ \node (q023) at (188bp,166.73bp) [draw,circle,state,final,accepting above] {$023$};
+ \node (q057) at (382bp,185.73bp) [draw,circle,state,final] {$057$};
+ \node (q0567) at (285bp,58.732bp) [draw,circle,state,final,accepting above] {$0567$};
+ \node (q02) at (100bp,160.73bp) [draw,circle,state] {$02$};
+ \node (q0237) at (285bp,166.73bp) [draw,circle,state,final,accepting below] {$0237$};
+ \node (q05) at (100bp,68.732bp) [draw,circle,state] {$05$};
+ \draw [->] (q057) ..controls (367.95bp,143.33bp) and (356.68bp,115.58bp) .. (340bp,95.732bp) .. controls (334.17bp,88.79bp) and (326.73bp,82.582bp) .. node[auto] {$b$} (q0567);
+ \draw [->] (q0) ..controls (45.352bp,134.58bp) and (60.273bp,141.85bp) .. node[auto] {$a$} (q02);
\draw [->] (q0237) to[loop above] node[auto] {$a$} (q0237);
- \draw [->] (q023) ..controls (213.27bp,203.14bp) and (232.48bp,225.93bp) .. (256bp,235.98bp) .. controls (287.74bp,249.53bp) and (326.56bp,235.18bp) .. node[auto] {$b$} (q057);
- \draw [->] (q023) ..controls (222.58bp,165.98bp) and (234.64bp,165.98bp) .. node[auto] {$a$} (q0237);
- \draw [->] (q02) ..controls (129.57bp,161.97bp) and (142.05bp,162.84bp) .. node[auto] {$a$} (q023);
+ \draw [->] (q023) ..controls (213.27bp,203.89bp) and (232.48bp,226.69bp) .. (256bp,236.73bp) .. controls (279.71bp,246.86bp) and (289.57bp,244.97bp) .. (314bp,236.73bp) .. controls (330.09bp,231.3bp) and (345.38bp,220.3bp) .. node[auto] {$b$} (q057);
+ \draw [->] (q023) ..controls (222.58bp,166.73bp) and (234.64bp,166.73bp) .. node[auto] {$a$} (q0237);
+ \draw [->] (q02) ..controls (129.57bp,162.73bp) and (142.05bp,163.6bp) .. node[auto] {$a$} (q023);
\draw [->] (q0567) to[loop below] node[auto] {$b$} (q0567);
- \draw [->] (q05) ..controls (129.65bp,64.644bp) and (142.24bp,63.18bp) .. node[auto] {$b$} (q056);
- \draw [->] (q027) ..controls (353.26bp,40.441bp) and (346.42bp,42.961bp) .. (340bp,44.975bp) .. controls (334.59bp,46.672bp) and (328.83bp,48.274bp) .. node[auto,above] {$b$} (q0567);
- \draw [->] (q056) ..controls (222.58bp,57.975bp) and (234.64bp,57.975bp) .. node[auto] {$b$} (q0567);
- \draw [->] (q0237) ..controls (323.66bp,181.04bp) and (337.58bp,186.61bp) .. node[auto] {$b$} (q057);
- \draw [->] (q056) ..controls (217.15bp,27.882bp) and (235.83bp,11.989bp) .. (256bp,4.9751bp) .. controls (287.46bp,-5.9647bp) and (325.21bp,4.3005bp) .. node[auto] {$a$} (q027);
- \draw [->] (q05) ..controls (100bp,99.927bp) and (100bp,116.29bp) .. node[auto] {$a$} (q02);
- \draw [->] (q057) ..controls (396.19bp,163.02bp) and (402.5bp,136.5bp) .. (400bp,112.95bp) .. controls (398.21bp,96.085bp) and (394.46bp,77.628bp) .. node[auto] {$a$} (q027);
- \draw [->] (q0567) ..controls (315.48bp,36.675bp) and (323.74bp,32.382bp) .. (332bp,29.975bp) .. controls (336.98bp,28.524bp) and (342.36bp,27.708bp) .. node[auto,below] {$a$} (q027);
- \draw [->] (q02) ..controls (115.85bp,134.18bp) and (120.35bp,121.75bp) .. (118bp,110.23bp) .. controls (116.93bp,104.99bp) and (115.19bp,99.598bp) .. node[auto] {$b$} (q05);
- \draw [->] (q0) ..controls (45.218bp,103.61bp) and (61.545bp,92.789bp) .. node[auto] {$b$} (q05);
+ \draw [->] (q05) ..controls (129.65bp,65.401bp) and (142.24bp,63.937bp) .. node[auto] {$b$} (q056);
+ \draw [->] (q056) ..controls (222.58bp,58.732bp) and (234.64bp,58.732bp) .. node[auto] {$b$} (q0567);
+ \draw [->] (q0237) ..controls (322.23bp,165.23bp) and (331.57bp,165.88bp) .. (340bp,167.73bp) .. controls (343.63bp,168.53bp) and (347.33bp,169.66bp) .. node[auto] {$b$} (q057);
+ \draw [->] (q056) ..controls (217.15bp,28.639bp) and (235.83bp,12.746bp) .. (256bp,5.7322bp) .. controls (280.35bp,-2.7337bp) and (288.93bp,-0.26493bp) .. (314bp,5.7322bp) .. controls (327.41bp,8.9409bp) and (341.18bp,15.299bp) .. node[auto,below] {$a$} (q027);
+ \draw [->] (q05) ..controls (100bp,100.68bp) and (100bp,117.05bp) .. node[auto] {$a$} (q02);
+ \draw [->] (q057) ..controls (397.04bp,148.37bp) and (402.36bp,127.76bp) .. (400bp,109.21bp) .. controls (398.44bp,96.972bp) and (395.4bp,83.809bp) .. node[auto] {$a$} (q027);
+ \draw [->] (q027) ..controls (362.81bp,75.635bp) and (351.82bp,95.041bp) .. (340bp,110.73bp) .. controls (332.19bp,121.1bp) and (322.64bp,131.57bp) .. node[auto] {$a$} (q0237);
+ \draw [->] (q0567) ..controls (324.14bp,51.105bp) and (336.81bp,48.57bp) .. node[auto,below] {$a$} (q027);
+ \draw [->] (q027) ..controls (382bp,87.723bp) and (382bp,124.52bp) .. node[auto] {$b$} (q057);
+ \draw [->] (q02) ..controls (115.85bp,134.94bp) and (120.35bp,122.5bp) .. (118bp,110.98bp) .. controls (116.93bp,105.75bp) and (115.19bp,100.36bp) .. node[auto] {$b$} (q05);
+ \draw [->] (q0) ..controls (45.218bp,104.36bp) and (61.545bp,93.546bp) .. node[auto] {$b$} (q05);
%
\end{tikzpicture}
diff --git a/figs/ex1p2c.dot b/figs/ex1p2c.dot
index 84317c1..b7ce3d3 100644
--- a/figs/ex1p2c.dot
+++ b/figs/ex1p2c.dot
@@ -19,18 +19,20 @@ digraph ex1p2c {
q05 -> q056 [label="b"];
q02 -> q023 [label="a"];
q056 -> q0567 [label="b"];
- q056 -> q027 [label="a"];
+ q056 -> q027 [label="a",lblstyle="auto,below"];
q023 -> q0237 [label="a"];
q023 -> q057 [label="b"];
{ rank="same"; q056; q023; }
q0567 -> q027 [label="a",lblstyle="auto,below"];
q027 -> q057 [label="b"];
- q057 -> q0237 [label="a"];
+ q057 -> q0237 [style="invis"];
q0237 -> q057 [label="b"];
q057 -> q027 [label="a"];
- q027 -> q0567 [label="b",lblstyle="auto,above"];
+ q027 -> q0567 [style="invis"];
{ rank="same"; q057; q027; }
{ rank="same"; q0567; q0237; }
q0237 -> q0237 [label="a",topath="loop above"];
q0567 -> q0567 [label="b",topath="loop below"];
+ q057 -> q0567 [label="b"];
+ q027 -> q0237 [label="a"];
}