State Machines

Why it matters

State Machines are fundamental in designing digital systems that require a sequence of operations, such as traffic lights, elevators, and digital watches. They help in modeling and implementing systems where the output depends not only on the current inputs but also on the history of inputs.

Key ideas

• State Machine: A model of computation representing a system with a finite number of states, transitions between those states, and actions.
• Types of State Machines:
  • Finite State Machine (FSM): Consists of a finite number of states and is used in control applications.
  • Mealy Machine: Outputs depend on the state and the input.
  • Moore Machine: Outputs depend only on the state.
• Components:
  • States: Different configurations that a system can be in.
  • Transitions: Rules that determine how the system moves from one state to another.
  • Inputs/Outputs: Signals that affect transitions and are produced by the system.

Formulas

• Q(t+1) = δ(Q(t), X(t))

  • Q(t+1): Next state
  • Q(t): Current state
  • X(t): Input
  • δ: State transition function

• Z(t) = λ(Q(t), X(t)) (Mealy Machine)

  • Z(t): Output
  • λ: Output function

• Z(t) = λ(Q(t)) (Moore Machine)

Worked example

Given: A Mealy Machine with states A and B, input X, and output Z. Transition from A to B occurs when X=1, and from B to A when X=0. Otherwise retain the state. Output Z=1 only when the current state is B and X=1, and Z=0 otherwise. The initial state is A, and each output is evaluated from the pre-transition state and current input.

1. Identify states and transitions: A, B
2. Define transition function:
   • If Q(t) = A and X(t) = 1, then Q(t+1) = B
   • If Q(t) = B and X(t) = 0, then Q(t+1) = A
3. Define output function:
   • If Q(t) = B and X(t) = 1, then Z(t) = 1
4. Calculate output for sequence X = [0, 1, 1, 0]:
   • Start at A, X=0: Stay at A, Z=0
   • X=1: Move to B, Z=0
   • X=1: Stay at B, Z=1
   • X=0: Move to A, Z=0

Final Answer: Output sequence Z = [0, 0, 1, 0]

Common mistakes

• Confusing Mealy and Moore machines.
• Incorrectly defining state transitions.
• Ignoring the effect of inputs on transitions and outputs.

For GATE EC

Questions often involve designing state machines, analyzing given state diagrams, or converting between Mealy and Moore machines. Practice defining state transition tables and diagrams.

Quick check

1. What is the main difference between a Mealy and a Moore machine?
2. How does a state machine transition from one state to another?
3. What determines the output in a Moore machine?

Answers: 1. Outputs depend on state and input in Mealy, only on state in Moore. 2. Through defined transition rules based on inputs. 3. The current state.