summaryrefslogtreecommitdiffstats
path: root/figs
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-10-29 16:25:25 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-10-29 16:25:25 (GMT)
commit086b4847f212f6d120ef59b659ed97c71d8fb897 (patch)
tree3bcc259c69e870f977fe4df270375228ccbff348 /figs
parentfdf0777a7cbba7fea7969d71aa128c5eb60a265d (diff)
downloadinf105-086b4847f212f6d120ef59b659ed97c71d8fb897.zip
inf105-086b4847f212f6d120ef59b659ed97c71d8fb897.tar.gz
inf105-086b4847f212f6d120ef59b659ed97c71d8fb897.tar.bz2
Describe the Thompson automaton of a regular expression.
Diffstat (limited to 'figs')
-rw-r--r--figs/example9.dot27
-rw-r--r--figs/example9b.dot19
2 files changed, 46 insertions, 0 deletions
diff --git a/figs/example9.dot b/figs/example9.dot
new file mode 100644
index 0000000..cd3526c
--- /dev/null
+++ b/figs/example9.dot
@@ -0,0 +1,27 @@
+digraph example9 {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial",label="0"];
+ q1 [style="state",label="1"];
+ q2 [style="state",label="2"];
+ q3 [style="state",label="3"];
+ q4 [style="state",label="4"];
+ q5 [style="state",label="5"];
+ q6 [style="state",label="6"];
+ q7 [style="state",label="7"];
+ q8 [style="state",label="8"];
+ q9 [style="state,final",label="9"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q1 [label="e",texlbl="$\varepsilon$"];
+ q1 -> q2 [label="e",texlbl="$\varepsilon$"];
+ q2 -> q3 [label="a"];
+ q3 -> q6 [label="e",texlbl="$\varepsilon$"];
+ q1 -> q4 [label="e",texlbl="$\varepsilon$"];
+ q4 -> q5 [label="b"];
+ q5 -> q6 [label="e",texlbl="$\varepsilon$"];
+ q6 -> q1 [label="e",texlbl="$\varepsilon$"];
+ q6 -> q7 [label="e",texlbl="$\varepsilon$"];
+ q0 -> q7 [label="e",texlbl="$\varepsilon$"];
+ q7 -> q8 [label="e",texlbl="$\varepsilon$"];
+ q8 -> q9 [label="b"];
+}
diff --git a/figs/example9b.dot b/figs/example9b.dot
new file mode 100644
index 0000000..78137c9
--- /dev/null
+++ b/figs/example9b.dot
@@ -0,0 +1,19 @@
+digraph example9b {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial",label="0"];
+ q5 [style="state",label="5"];
+ q3 [style="state",label="3"];
+ q9 [style="state,final",label="9"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q3 [label="a"];
+ q0 -> q5 [label="b"];
+ { rank="same"; q3; q5; }
+ q3 -> q3 [label="a",topath="loop above"];
+ q5 -> q5 [label="b",topath="loop below"];
+ q3 -> q5 [label="b",lblstyle="auto,swap,near end"];
+ q5 -> q3 [label="a",lblstyle="auto,swap,pos=-0.2"];
+ q0 -> q9 [label="b"];
+ q3 -> q9 [label="b"];
+ q5 -> q9 [label="b"];
+}