Computation - Intro to Automaton (part 1)

Using Pictures for Patterns

Imagine if someone told you to check a queue of an unknown length to see if it contained an even number of zombies. How would you do it?



More than likely you will remember whether you have seen an odd number of zombies, or an even number. If we wished to produce an image of this, it may look like this:

note: 0=zombie

So, every time we see a ‘zombie’, we switch from the EVEN state to the ODD state, and vice-versa.

Now we have this, what would you do if you saw a ‘non-zombie (human)’? Well, with this current image nothing. So let’s add in some arrows for the ‘human’s. Also, we need to tell the person which state that they are required to start in, so lets throw that in as well. So now we have:

note: 1=human (non-zombie)

The way we show which state they need to start in, is declared via the arrow that points from nothing to the EVEN state, this is known as the start state. Now that this is done, we need to think. How do we know whether we have finished in the EVEN or the ODD state? This is declared by a double-ringed state, also known as an accepting state.

-------------------------------------------------------------------------------------------------------

Lets take this idea to another problem. Lets say, for example, that we are interested in whether a given queue has a ‘zombie’ in every position that is a multiple of 2, such as positions 2, 4, 6 etc. So we need to start in some state, and for the first person, we don’t really care what it is, either a ‘zombie’ or a ‘human’ will do here. So first we have something like this:

Now for the final state, this time if we see a ‘zombie' we’re OK, but if we see a ‘human’ we need to reject it the given queue. We also need to include the accepting states so that we end up with:

Now all we need to do it neaten it up a little. Namely we need to say that if we are in state 1 and see a ‘zombie’, go back to state 0 rather than to a new state 2.

There we go, thats much better :) , so now when were in state 1 and see a 'zombie' we go to state 0, or if we see a 'human' we go to state 3, also known as a dump state.

That’s the end of the intro to automatons, next we see Finite State Automata such as NFAs and DFAs.