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.