From 724a5e10fd98080f49709ec5081fe1ff41c73625 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 30 Nov 2016 17:55:20 +0100 Subject: Fix mistake in minimization of automaton. --- exercices1.tex | 50 +++++++++++++++++++++++++------------------------- figs/ex1p2c.dot | 8 +++++--- 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"]; } -- cgit v1.2.3