Bringing Theoretical Class Work to Life: Meet My Pal the DFA

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.