# Finite State Machines

Learn about transition graphs, and look at a few examples of 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$.

Get hands-on with 1200+ tech skills courses.