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

State51025OR‖51025OR
next state‖output
‖nnnnn
‖nnnnn
‖nn5nn
‖nn10nn
‖nn15nn
‖n520nn
‖51025OJAJ

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
10
11
01
00
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

Input101011—
State
Output001000—

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.)
Stateinput 00011011
(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

TypeOutput depends onNamed after
Mealy machine (this section)the transition (state + input)G. H. Mealy, 1955
Moore machinethe state onlyE. 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.