Just to prove it was quite easy to do, and also to show to my friends in Automata that the stuff might be more practical than they think, I put together an actual implementation of the Problem 11, an ugly DFA assigned to us as homework. Problem 11 was to prove that L = { vwv : v, w ∈ {a, b}*, |v| = 2} defines a regular language. The easiest way to do this is to build the DFA. In this case the DFA is a large 19 state system.
Here's the diagram (generated with Graphviz's dot):
Here's the DOT file code that generated this (color highlighting by VIM):
digraph prob11 {
q0 [style=filled, color=green];
q9 [shape=doublecircle];
q12 [shape=doublecircle];
q15 [shape=doublecircle];
q18 [shape=doublecircle];
q0 -> q1 [label=a];
q0 -> q2 [label=b];
q1 -> q3 [label=a];
q1 -> q4 [label=b];
q2 -> q5 [label=a];
q2 -> q6 [label=b];
q3 -> q8 [label=a];
q3 -> q7 [label=b];
q4 -> q11 [label=a];
q4 -> q10 [label=b];
q5 -> q13 [label=a];
q5 -> q14 [label=b];
q6 -> q16 [label=a];
q6 -> q17 [label=b];
q7 -> q8 [label=a];
q7 -> q7 [label=b];
q8 -> q9 [label=a];
q8 -> q7 [label=b];
q9 -> q9 [label=a];
q9 -> q7 [label=b];
q10 -> q11 [label=a];
q10 -> q10 [label=b];
q11 -> q11 [label=a];
q11 -> q12 [label=b];
q12 -> q11 [label=a];
q12 -> q10 [label=b];
q13 -> q13 [label=a];
q13 -> q14 [label=b];
q14 -> q15 [label=a];
q14 -> q14 [label=b];
q15 -> q13 [label=a];
q15 -> q14 [label=b];
q16 -> q16 [label=a];
q16 -> q17 [label=b];
q17 -> q16 [label=a];
q17 -> q18 [label=b];
q18 -> q16 [label=a];
q18 -> q18 [label=b];
}
...and with a few simple changes to that I created the Haskell file:
q 0 [] = False
q 1 [] = False
q 2 [] = False
q 3 [] = False
q 4 [] = False
q 5 [] = False
q 6 [] = False
q 7 [] = False
q 8 [] = False
q 9 [] = True
q 10 [] = False
q 11 [] = False
q 12 [] = True
q 13 [] = False
q 14 [] = False
q 15 [] = True
q 16 [] = False
q 17 [] = False
q 18 [] = True
q 0 ('a':xs) = q 1 xs
q 0 ('b':xs) = q 2 xs
q 1 ('a':xs) = q 3 xs
q 1 ('b':xs) = q 4 xs
q 2 ('a':xs) = q 5 xs
q 2 ('b':xs) = q 6 xs
q 3 ('a':xs) = q 8 xs
q 3 ('b':xs) = q 7 xs
q 4 ('a':xs) = q 11 xs
q 4 ('b':xs) = q 10 xs
q 5 ('a':xs) = q 13 xs
q 5 ('b':xs) = q 14 xs
q 6 ('a':xs) = q 16 xs
q 6 ('b':xs) = q 17 xs
q 7 ('a':xs) = q 8 xs
q 7 ('b':xs) = q 7 xs
q 8 ('a':xs) = q 9 xs
q 8 ('b':xs) = q 7 xs
q 9 ('a':xs) = q 9 xs
q 9 ('b':xs) = q 7 xs
q 10 ('a':xs) = q 11 xs
q 10 ('b':xs) = q 10 xs
q 11 ('a':xs) = q 11 xs
q 11 ('b':xs) = q 12 xs
q 12 ('a':xs) = q 11 xs
q 12 ('b':xs) = q 10 xs
q 13 ('a':xs) = q 13 xs
q 13 ('b':xs) = q 14 xs
q 14 ('a':xs) = q 15 xs
q 14 ('b':xs) = q 14 xs
q 15 ('a':xs) = q 13 xs
q 15 ('b':xs) = q 14 xs
q 16 ('a':xs) = q 16 xs
q 16 ('b':xs) = q 17 xs
q 17 ('a':xs) = q 16 xs
q 17 ('b':xs) = q 18 xs
q 18 ('a':xs) = q 16 xs
q 18 ('b':xs) = q 18 xs
...and loading that into a Haskell interpreter I can then "run" the dfa and test some sample inputs for acceptance.
___ ___ _
/ _ / // __(_)
/ /_// /_/ / / | | GHC Interactive, version 6.4, for Haskell 98.
/ /_\/ __ / /___| | http://www.haskell.org/ghc/
____// /_/____/|_| Type :? for help.
Loading package base-1.0 ... linking ... done.
Compiling Main ( prob11.hs, interpreted )
Ok, modules loaded: Main.
*Main> q 0 "ab"
False
*Main> q 0 "aaaa"
True
*Main> q 0 "aaaaab"
False
*Main> q 0 "aaaaabbbb"
False
*Main> q 0 "aaaabbbb"
False
*Main> q 0 "bbbb"
True
*Main> q 0 "bbbbbbaaaaaa"
False
*Main> q 0 "babaaaaaaba"
True
*Main> q 0 "abbbbab"
True
*Main> q 0 "abab"
True
So, as far as I can tell, this crazy convoluted DFA does do the job, and the answer to the given problem is the language is regular. I just wanted to show that with surprisingly little work I had a working "model" and pretty graph. I guess that's pretty geeky and none of my friends actually care, but I felt like sharing.