We now switch from a study of languages to a study of machines (automata). Why? You will see!

Finite automata (FA) are most clearly described by pictures (state diagrams):

FA vocabulary:

• circles are called states
• each has a distinct label or name (here, 1, 2, 3, 4, 5)
• there can be only finitely many states (thus the name)
• double circles: a special kind of state called a final state
• can be 0 or more of these
• circle with arrow ® coming from nowhere
• there must be exactly 1 of them
• it's called the start state (or initial state)
• labeled arrows between states are called transitions
• arrow labels are from a vocabulary of characters
• and are called transition symbols
• transitions from a given state must all be labeled differently

How does a state diagram behave like a machine?

Here's how it "works":

1. you are given an input string of characters
2. machine "starts" in its start state
3. "read" the first character from the input string
4. delete that character from the string
5. from the current state, take the transition indicated by the input character, and "move" to the indicated state (if there is no transition, CRASH and reject the string
6. if the input string is not empty, go back to 3
7. otherwise, if the machine is in a final state, accept the string. If not, reject it.

Let's see if "aaab" will be accepted:
 

state input 1 aaab 2 aab 2 ab 2 b 4 l ACCEPT

We can also encode a FA in tabular (array) format:
 

	Transition symbol
State	a	b	c	d
1 Start	2	3	3
2	2	4	4
3			3	5
4 Final
5 Final

This suggests one way to program an FA on a computer!

Another example:

("+"+- +l )(1+2+…+9)(0+1+2…+9)*( l +.)(0+1+2…+9)*