2IC30Computer Systems

2IC30 · assessment

Q3 FSM trainer

Five exam scenarios with staged model answers for states, tables and equations.

Finite state machine scenarios

The method (do this every time)

  • List states from the scenario's distinct behaviours, name them meaningfully, and mark the start state.
  • Decide Moore versus Mealy — the exam usually wants Moore, with the output written inside each state.
  • Write each state's outputs.
  • Draw transitions with guard conditions on the inputs, covering every input combination with a stay default.
  • Encode the states in the dictated bits.
  • Build the output table and the transition table.
  • Karnaugh each next-state bit and output into gates, then implement the state with clocked D flip-flops.

Scenario Description

An autonomous warehouse patrol robot needs an FSM controller. The system has four inputs: k (docked), b (battery full), o (obstacle), and c (charge complete). The output is m (move) which drives the robot's motors, and a status indicator light output n.

Behavior rules:

Scenario Description

  • The robot starts in an Idle state (docked, waiting for battery).
  • It starts patrolling when the battery is full and charge is complete.
  • If it encounters an obstacle while patrolling, it must stop and wait until the obstacle is removed.
  • Once patrolling is finished and it returns to the dock (k=1), it returns to the Idle state.
  • If charging is complete but the battery is not full, it must enter a Fault state (no move). It can only leave this state to the Idle state when the battery becomes full.

Tasks:

  • Draw a state transition diagram of a Moore machine implementing the controller. Label all states and transition conditions.
  • Construct the output table and next-state transition table using the following state encoding: Idle = 00, Patrolling = 01, ObstacleWait = 11, Fault = 10 (state bits s and t).
  • Assuming you are given the minimized next-state and output boolean equations, draw a circuit using clocked D-flip-flops.

Attempt each part on paper first, then reveal to check.

Order the FSM design method

The seven steps from "The method (do this every time)", in the order they're worked.

0/1 ordered

Put the FSM design method steps in order.

  1. Decide Moore versus Mealy — the exam usually wants Moore, with the output written inside each state.
  2. Write each state's outputs.
  3. Draw transitions with guard conditions on the inputs, covering every input combination with a stay default.
  4. Encode the states in the dictated bits.
  5. Build the output table and the transition table.
  6. Karnaugh each next-state bit and output into gates, then implement the state with clocked D flip-flops.
  7. List states from the scenario's distinct behaviours, name them meaningfully, and mark the start state.