Finite State Machines

Transition graphs

We design our computations to only consider one symbol at a time, making decisions based only on the current “state” and the current input symbol. Consider the language $L$:

$$L=\{ \lambda, aa, ab, ba, bb, aaaa, aaab, aaba, aabb, abaa,\cdots \}$$

For this language, we only need to know whether or not the number of symbols consumed at any point is even.

Since integers are either even or odd, we have only two states (evenness vs. oddness) to consider. The transition graph in the figure below depicts a two-state, abstract machine that will solve our problem; we have only to observe whether or not an input string causes the machine to halt in the “even” state, $E$.

The start state is $E$, indicated by an incoming arrow from “out of nowhere.” The edges between states $E$ ...