Page Comparison

...

We can abstract this sort of decision-making process into a graph. Every state in the program is represented as a circle, and transitions between states can be represented by drawing unidirectional arrows between them, labelled with what the transition is. In the above example, states might be partial matches we have matched so far, and state transitions might be labelled by the next bit that is read. This sort of program is known as a state machine. States are the individual configurations of the program based on the inputs seen, and the diagrams we draw are called deterministic finite automata (or DFAs).

Image Removed

A circle within a circle (or a circle with a double border) accepts—it represents a state that, if the input ends there, we can simply accept it as valid, and we can use it as an end state. A circle with an arrow pointing into it from the left represents the start state. The * on the final state denotes any other value in the language (ie. all the valid inputs, which is either 0 or 1, in this case).

Take some time to convince yourself that this graph representation of an automata is the same as the algorithm presented above. 

Note: If you want to recreate this image, I just used graphviz, which makes drawing these super easy.

 digraph finite_state_machine {
     rankdir=LR;
     size="8,5"
 
     node [shape = circle]; start;
     node [shape = doublecircle]; 010;
     node [shape = point ]; qi
 
     node [shape = circle];

     qi    -> start;
     start -> 0     [ label = "0" ];
     0     -> 01    [ label = "1" ];
     01    -> 010   [ label = "0" ];
     0     -> start [ label = "0" ];
     01    -> start [ label = "1" ];
     010   -> 010   [ label = "*" ];
 }

and then render the PNG.

dot -Tpng fsm.gv -o example-fsm.png

...

 Applications of Finite State Machines

Well, whoop-de-doo, that's great and all, but how does matching binary strings relate to writing firmware for a solar car? Recall our earlier definition of a Finite State Machine:

...