Activity 4.1.2 — State Machines

Learning Objectives

By the end of this lesson, students will be able to:

1. Define what a state machine is and its components
2. Distinguish between Moore and Mealy machines
3. Draw state diagrams for sequential systems
4. Create state tables from state diagrams
5. Design a simple state machine using flip-flops

Vocabulary

Part 1: What is a State Machine?

Definition

A state machine is a mathematical model that describes a system that:

1. Can be in one of a finite number of states
2. Can transition between states based on inputs
3. Produces outputs based on the current state (and possibly inputs)

Real-World Examples

Part 2: Moore vs Mealy Machines

Moore Machine

Outputs depend only on the current state.

Inputs ──────┐
             │
             ▼
        ┌─────────┐
        │         │
  State │  Logic  │──────▶ Outputs
  (FFs) │         │
        └────┬────┘
             │
             ▼
          Clock

Example: Traffic Light

• State: GREEN → Output: Green light ON
• State: YELLOW → Output: Yellow light ON
• State: RED → Output: Red light ON

Mealy Machine

Outputs depend on current state AND inputs.

Inputs ──────┐
             │
        ┌────▼────┐
        │         │
  State │  Logic  │──────▶ Outputs
  (FFs) │         │
        └────┬────┘
             │
             ▼
          Clock

Example: Edge Detector

• State: LOW, Input: 0 → Output: 0
• State: LOW, Input: 1 → Output: 1 (transition to HIGH)
• State: HIGH, Input: 1 → Output: 0 (no change)
• State: HIGH, Input: 0 → Output: 0 (transition to LOW)

Key insight: Mealy machines often require fewer states than Moore machines because outputs can change immediately based on inputs, not just on state changes.

Part 3: State Diagrams

State diagrams use circles for states and arrows for transitions.

Notation

        ┌─────────┐
        │  State  │   (circle = state)
        │    A    │
        └────┬────┘
             │ Input/Output
             ▼ (arrow = transition)

Example: Traffic Light Controller

Problem: Design a traffic light that cycles Green → Yellow → Red → Green

State Diagram:

         Timer = 30s              Timer = 5s
    ┌──────────────▶┌──────────────┐
    │               │              │
    │               │              │
    │         ┌─────▼─────┐        │
    │         │   GREEN   │        │
    │         └─────┬─────┘        │
    │ Timer = 30s  │               │
    │               │ Timer = 5s   │
    │               ▼               │
    │         ┌─────────┐          │
    │         │ YELLOW  │──────────┘
    │         └────┬────┘
    │              │ Timer = 5s
    │              ▼
    │        ┌─────────┐
    │        │   RED   │─────────────┐
    │        └─────────┘             │
    │                                │
    └────────────────────────────────┘
              Timer = 30s

Transition Labels

• Moore: Label the arrow with just the input
• Mealy: Label the arrow with “Input/Output”

Example Mealy (button press detector):

           1/1 (press)              0/0
    ┌──────────────▶┌──────────────┐
    │               │  Pressed      │
    │               └──────┬───────┘
    │               0/0    │
    │                      │
    └──────────────────────┘
           0/0 (no press)

Part 4: State Tables

A state table shows all possible combinations of current state and inputs.

Example: Traffic Light State Table

Encoding:

• S0 = GREEN
• S1 = YELLOW
• S2 = RED

State Table:

Part 5: State Machine Design Process

Step-by-Step Process

1. Define the problem - What inputs, outputs, and states are needed?
2. Draw the state diagram - Show all states and transitions
3. Create the state table - List all state/input combinations
4. Assign binary codes - Each state gets a unique binary pattern
5. Choose flip-flop type - JK or D flip-flops are common
6. Derive input equations - Use Karnaugh maps or truth tables
7. Draw the circuit - Implement with flip-flops and gates

Example: Design a “101” Sequence Detector

Problem: Detect the sequence 1-0-1 in a serial input stream.

Step 1: Define states

• S0: No 1s detected (initial)
• S1: One 1 detected
• S2: Sequence 1-0 detected, waiting for final 1
• S3: Sequence 1-0-1 detected (output = 1)

Step 2: State Diagram

          Input = 1           Input = 0         Input = 1
    ┌──────────────▶┌───────────────▶┌──────────────┐
    │               │               │              │
    │         ┌─────▼─────┐   ┌─────▼─────┐      │
    │         │    S0     │   │    S1     │      │
    │         │  (initial)│   │ (got '1') │      │
    │         └─────┬─────┘   └─────┬─────┘      │
    │ Input = 0    │               │Input = 1   │
    │              ▼               │            │
    │         ┌─────────┐         ▼            │
    │         │   S2    │◀──┌─────────┐        │
    │         │ (got 10)│   │   S3    │────────┘
    │         └─────────┘   │(101 found)│ Output=1
    │                         └─────────┘   Input=1 (stay)
    └───────────────────────────────────────────
                 Input = 0

Step 3: State Table

Step 4: State Encoding

• S0 = 00
• S1 = 01
• S2 = 10
• S3 = 11

Part 6: Implementing State Machines

Using D Flip-Flops

For each flip-flop, determine what D input is needed to achieve the next state.

Deriving Input Equations

From the state table, create a truth table for each flip-flop input:

For Q1 (MSB):

Simplify using Karnaugh map: D1 = Q1·Q0 + Q1·Input + Q0·Input

Part 7: Practice Problem

Problem Statement

Design a state machine that monitors a single input button. When the button is pressed three times, turn on an LED.

Requirements:

1. Input: Pushbutton (HIGH when pressed)
2. Output: LED (turns ON after 3 presses)
3. Use Moore machine approach
4. Draw state diagram and create state table

States needed:

• S0: No presses counted
• S1: One press counted
• S2: Two presses counted
• S3: Three presses counted (LED ON)

         Button = 1         Button = 1        Button = 1
    ┌──────────────▶┌──────────────▶┌──────────────┐
    │               │               │              │
    │         ┌─────▼─────┐   ┌─────▼─────┐   ┌─────▼─────┐
    │         │    S0     │   │    S1     │   │    S2     │
    │         │  (0) LED:0│   │  (1) LED:0│   │  (2) LED:0│
    │         └─────┬─────┘   └─────┬─────┘   └─────┬─────┘
    │               │               │               │
    │               │Button=0       │Button=0       │Button=0
    │               ▼               ▼               ▼
    │         (stay in same state when button not pressed)
    │
    │Button = 1
    │
    └───────────────▶┌──────────────┐
                     │    S3        │
                     │  (3) LED:1   │
                     └──────┬───────┘
                            │
                            │Button = 0
                            ▼
                        (reset to S0)

Summary

• A state machine has states, transitions based on inputs, and outputs
• Moore machines: outputs depend only on current state
• Mealy machines: outputs depend on state AND inputs
• State diagrams visualize states (circles) and transitions (arrows)
• State tables list current state, inputs, next state, and outputs
• Design process: define states → draw diagram → create table → encode → derive equations → implement

Key Reminders

• Start with state diagram to visualize the problem
• Use binary encoding (00, 01, 10, 11) for each state
• Karnaugh maps simplify flip-flop input equations
• Moore machines are often easier to implement (outputs stable after clock)
• Mealy machines can use fewer states

Custom activity — adapted from PLTW Digital Electronics