A machine that answers yes or no
A finite automaton, also called a finite state machine, is the simplest model of a computer. It reads a string of symbols one at a time and ends by accepting or rejecting it.
A network card uses one to check that a frame of bits has an even number of ones. This lesson shows you how to trace such a machine by hand, and then run it in Python.
By the end of this lesson
Note
I can trace a finite automaton and say which strings it accepts.
Key words
| Word | What it means | Example |
|---|---|---|
| Alphabet | the symbols a machine can read | 0 and 1 |
| State | what the machine remembers right now | even |
| Transition | a rule: in this state, reading this symbol, move to that state | |
| Start state | the state the machine is in before it reads anything | |
| Accepting state | a state that means yes if the input ends there | |
| Accept | to finish reading the input in an accepting state |
The cells students fill in are left blank in this preview.
A machine is states and transitions
A finite automaton has a fixed, small number of states. At any moment it is in exactly one of them.
It reads the input left to right, one symbol at a time. Each symbol moves it along a transition to the next state. When the input runs out, the machine accepts if it is in an accepting state, and rejects if not.
Worked example: an even-number-of-ones checker
| State | Reads 0 | Reads 1 | Role |
|---|---|---|---|
| even | even | odd | Start state, accepting |
| odd | odd | even | Not accepting |
The cells students fill in are left blank in this preview.
Tracing the input 1011 step by step
| Step | Symbol read | State before | State after |
|---|---|---|---|
| 1 | 1 | even | odd |
| 2 | 0 | odd | odd |
| 3 | 1 | odd | even |
| 4 | 1 | even | odd |
| End | Nothing left | odd | Rejected: three ones is odd |
The cells students fill in are left blank in this preview.
The machine remembers only its state
The machine never stores the input. After 1011 it does not know the string was four symbols long. It knows one fact: the number of ones so far is odd.
That is why the memory is finite. Two states can only remember two facts, however long the input is.
A common mistake
Warning
Many people think an automaton remembers everything it has read. It remembers only which state it is in. Use an automaton when one small fact is enough, such as odd or even. When you need to remember a count that can grow without limit, a finite automaton cannot do it.
The rule table is a dictionary
The table above becomes a dictionary of dictionaries in Python. The outer key is the state and the inner key is the symbol.
The loop is the whole machine: look up the next state, move to it, repeat. Run it, then change the input.
The parity machine in Python
# A finite automaton as a table: for each state, where each symbol leads.
RULES = {
"even": {"0": "even", "1": "odd"},
"odd": {"0": "odd", "1": "even"},
}
text = "1011"
state = "even"
for symbol in text:
state = RULES[state][symbol]
print(symbol, "leads to", state)
if state == "even":
print("accepted")
else:
print("rejected")
# Change text to "1001" and run again.
Check the machine in the lab shell
You can check the machine's answer another way. Count the ones in the string: an even count means accepted. In the shell, tr -d 0 deletes the zeros, and wc -c counts what is left. The lexer you meet in the compilers module is built from machines like this one.
Count the ones in 1011
printf '1011' | tr -d 0 | wc -cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Count the ones in 1001
printf '1001' | tr -d 0 | wc -cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Ask Python whether 1011 has an even count
python3 -c "print('1011'.count('1') % 2 == 0)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Going further
Draw the table for a machine that accepts a string of 0s and 1s only if it has no two 1s in a row. It needs a third state for the moment two 1s have appeared.
Say what the machine does after reaching that state, and why it can never leave it.