1. Introduction
Every finite-state machine has: a finite set of states with a designated start state, an input alphabet, and a transition function (next state for every state/input pair).
Used in: spell/grammar checking, text indexing and search, speech recognition, XML/HTML processing, network protocols, and hardware components.
2. Motivating Example: Vending Machine
- Accepts 5¢, 10¢, 25¢. Once ≥ 30¢ is deposited, it immediately refunds the excess.
- Then the customer presses O (orange juice) or R (apple juice).
- States : = ” cents collected”. Start in .
- Inputs: 5, 10, 25, O, R. Outputs: n (nothing), 5, 10, 15, 20, 25 (change), OJ, AJ.
Table 1 — state table
| State | 5 | 10 | 25 | O | R | ‖ | 5 | 10 | 25 | O | R |
|---|---|---|---|---|---|---|---|---|---|---|---|
| next state | ‖ | output | |||||||||
| ‖ | n | n | n | n | n | ||||||
| ‖ | n | n | n | n | n | ||||||
| ‖ | n | n | 5 | n | n | ||||||
| ‖ | n | n | 10 | n | n | ||||||
| ‖ | n | n | 15 | n | n | ||||||
| ‖ | n | 5 | 20 | n | n | ||||||
| ‖ | 5 | 10 | 25 | OJ | AJ |
Pressing a button before reaching 30¢ does nothing; extra coins in are returned. The same machine can be drawn as a state diagram (circles = states, edges labeled input, output).
3. Formal Definition
Definition 1
A finite-state machine :
- — finite set of states
- — finite input alphabet
- — finite output alphabet
- — transition function: (state, input) → next state
- — output function: (state, input) → output
- — initial state
Representations:
- State table — values of and for every (state, input).
- State diagram — directed graph; each edge labeled with the input, output pair.
Example (Table 2 / Figure 2): ,
| State | : input 0 | : input 1 | : input 0 | : input 1 |
|---|---|---|---|---|
| 1 | 0 | |||
| 1 | 1 | |||
| 0 | 1 | |||
| 0 | 0 |
graph LR start(( )) --> s0 s0 -->|"0, 1"| s1 s0 -->|"1, 0"| s0 s1 -->|"0, 1"| s3 s1 -->|"1, 1"| s0 s2 -->|"0, 0"| s1 s2 -->|"1, 1"| s2 s3 -->|"0, 0"| s2 s3 -->|"1, 0"| s1
4. Input Strings → Output Strings
Reading from left to right:
- states: ,
- outputs:
The output string is , and we extend to strings: .
Example (Figure 3 — a 5-state machine –, different from Table 2): input 101011 → output 001000
| Input | 1 | 0 | 1 | 0 | 1 | 1 | — |
|---|---|---|---|---|---|---|---|
| State | |||||||
| Output | 0 | 0 | 1 | 0 | 0 | 0 | — |
Tip: build a trace table like this — row of inputs, row of states (one more than inputs), row of outputs.
5. Useful Machines
States give an FSM limited memory: they remember properties of what has been read. Because there are only finitely many states, some tasks are impossible (§13.4).
Example 5 — Unit-delay machine
Output the input delayed by one step: input → output .
- = start; = “previous input was 1”; = “previous input was 0”.
- First output is 0; every transition out of outputs 1, out of outputs 0.
graph LR start(( )) --> s0 s0 -->|"1, 0"| s1 s0 -->|"0, 0"| s2 s1 -->|"1, 1"| s1 s1 -->|"0, 1"| s2 s2 -->|"0, 0"| s2 s2 -->|"1, 0"| s1
Example 6 — Binary adder
Add , feeding bit pairs from right to left. Each stage adds giving sum bit and carry .
- Only two states: = previous carry 0 (start), = previous carry 1.
- Inputs: 00, 01, 10, 11. Output = sum bit. (Assume so the final carry fits.)
| State | input 00 | 01 | 10 | 11 |
|---|---|---|---|---|
| (carry 0) | , out 0 | , out 1 | , out 1 | , out 0 |
| (carry 1) | , out 1 | , out 0 | , out 0 | , out 1 |
e.g. in with input 01: → output 0, stay in .
Example 7 — Detect three consecutive 1s
Output 1 iff the last three bits read are all 1.
- : previous input was not 1 (or none) · : last input 1, the one before not · : last two inputs were 1s.
- Input 0 sends every state to . Input 1: .
- Only the transition outputs 1; all others output 0.
graph LR start(( )) --> s0 s0 -->|"0, 0"| s0 s0 -->|"1, 0"| s1 s1 -->|"0, 0"| s0 s1 -->|"1, 0"| s2 s2 -->|"0, 0"| s0 s2 -->|"1, 1"| s2
6. Language Recognition with Output
Definition 2
recognizes (accepts) iff the last output bit is 1 exactly when the input string is in .
Example 7 recognizes the set of bit strings that end with 111.
7. Types of Finite-State Machines
| Type | Output depends on | Named after |
|---|---|---|
| Mealy machine (this section) | the transition (state + input) | G. H. Mealy, 1955 |
| Moore machine | the state only | E. F. Moore, 1956 |
| Finite-state automaton (§13.3) | no output — has final states | — |
For language recognition we usually use finite-state automata: a string is accepted iff it takes the start state to a final state.