sasbury.com

Chapter 2 of the The New Turing Omnibus is about Finite Automata. I wanted to do some of the exercises on the blog so I looked around for a good way to draw finite state diagrams. Looks like graphviz is the standard. I thought it would be easier if I could just write my graphviz code in my markdown, so I looked around some more and found this discussion on stack overflow. There is a pointer to a version of graphviz compiled with llvm and emscripten on github. So I updated my pages to automatically process pre.graphviz tags as input for graphviz. Below are the results for some of the exercises at the end of chapter 2.

The core code is:

    svg = Viz(graphvizCode, 'svg');
    $('#svg-'+index).html(svg);

Each exercise is to describe the finite automata that accept the following languages.

I haven't drawn a lot of these, so comments are welcome.

(ab)*(a+b)*

The first exercise is to find the automata that processes (ab)\*(a+b)\*. I read this as:

1. read a
2. read b
3. go back to 1, or continue
4. read a or read b
5. go back to 4 or finish

As a finite state machine, i see this as:

digraph finite_state_machine {
    rankdir=LR;
    size="5,5"
    node [shape = point]; start;
    node [shape = doublecircle]; end;
    node [shape = circle];
    start -> 1 [ label = "a" ];
    1 -> 2 [ label = "b" ];
    2 -> 1 [label = "a"];
    2 -> end [label = "a"];
    2 -> end [label = "b"];
    end -> end [label = "a"];
    end -> end [label = "b"];
}

but this is the one I am least sure about. I am not sure if I am using the states 1 and 2 correctly.

0 + 1

The second language is 0 + 1 which I see as match 0 or 1 and then you are done.

digraph finite_state_machine {
    rankdir=LR;
    size="5,5"
    node [shape = point]; start;
    node [shape = doublecircle]; end;
    start -> end [ label = "0" ];
    start -> end [ label = "1" ];
}

0* + 1

The final exercise is the language 0* + 1. This means match "1 or more" zeros or a 1. After matching, the language is finished.

digraph finite_state_machine {
    rankdir=LR;
    size="5,5"
    node [shape = point]; start;
    node [shape = doublecircle]; end; end_2;
    start -> end_2 [ label = "0" ];
    end_2 -> end_2 [label = "0"]
    start -> end [ label = "1" ];
}

I really like thinking about these finite automata because, as Dewdney says, finite automata are basically equivalent to regular expressions. I have started to use regular expressions a lot more over the last year and find them to be a really amazing tool once you start to internalize them.