## Finite Automata

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:

- read a
- read b
- go back to 1, or continue
- read a or read b
- go back to 4 or finish

As a finite state machine, i see this as:

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.

### 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.

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.