Finite State Machines — Mealy and Moore Models Introduction

What is a Finite State Machine?

A Finite State Machine (FSM) is a mathematical model of computation with a finite number of states, where the system is in exactly one state at any time. State transitions occur based on inputs, and outputs are produced.

Components of an FSM:

• States (Q): Finite set of internal states
• Input alphabet (Σ): Set of possible inputs
• Output alphabet (Λ): Set of possible outputs
• Transition function (δ): δ(current_state, input) → next_state
• Output function (λ): Produces outputs
• Initial state (q₀): Starting state
• Final/accepting states: (for language recognition)

Mealy Machine

In a Mealy machine, the output depends on both current state AND input.

State diagram notation:

Characteristics:

• Output can change immediately when input changes (within a clock cycle)
• Fewer states needed than Moore for same function
• Output labeled on transitions (not states)
• Faster response to inputs

Moore vs Mealy Comparison

Equivalence: Any Mealy machine can be converted to a Moore machine (with possibly more states) and vice versa.

State Diagram → State Table

Example: Design a Moore FSM that detects sequence "101" in a serial bit stream.

States: S0 (initial), S1 (got 1), S2 (got 10), S3 (got 101 — output 1)

State Diagram:

State Table:

State Equations from State Table

Assign state variables: S0=00, S1=01, S2=10, S3=11 Let current state = Y1Y0, input = X, output = Z

Next state equations (derived from state table, then K-map minimization):

FSM Design Procedure

1. Problem statement → identify inputs, outputs, state behavior
2. Draw state diagram (circles = states, arrows = transitions)
3. Create state table (current state, input → next state, output)
4. State minimization (merge equivalent states)
5. State assignment (assign binary codes to states)
6. Derive next-state and output equations (using K-maps)
7. Choose flip-flop type (D, JK, T) and derive excitation equations
8. Draw circuit and verify

Interview Questions

Q1: What is the key difference between Moore and Mealy machines? In Moore machines, output depends only on the current state. In Mealy machines, output depends on both current state and current input. Mealy machines are generally more efficient (fewer states) but outputs can change mid-cycle. Moore machines have synchronized, glitch-free outputs.

Q2: How do you convert a Mealy machine to a Moore machine? For each Mealy state S with multiple different outputs on different transitions, create separate Moore states (one per unique output). The new Moore states produce the corresponding outputs. This typically increases the number of states.

Q3: What is state minimization and why is it important? State minimization finds the smallest equivalent FSM by merging states that are indistinguishable (produce the same output for all input sequences). It reduces hardware cost — fewer states means fewer flip-flops and simpler logic.

Q4: What determines the number of flip-flops needed in an FSM? The number of flip-flops r = ⌈log₂(N)⌉, where N is the number of states. For 4 states: 2 flip-flops. For 5–8 states: 3 flip-flops. For 9–16 states: 4 flip-flops.

Q5: In a sequence detector, what advantage does a Mealy implementation have? A Mealy sequence detector can produce output in the same clock cycle the final input is received, while a Moore detector adds one clock cycle of latency (the output appears in the state reached after the final input). For time-critical systems, Mealy is preferred.