Learning Objectives
By the end of this lesson, you will be able to:
- Show understanding of the purpose of state-transition diagrams to document an algorithm
- Understand the concept of a Finite State Machine (FSM) as a mathematical model
- Interpret state-transition tables and diagrams
- Construct state-transition diagrams for given algorithms
- Identify states, transitions, events, and conditions in FSM diagrams
- Apply state-transition diagrams to real-world problems like security systems and binary conversion
Key Terms
Finite State Machine (FSM)
A mathematical model of a machine that can be in one of a fixed set of possible states
State
A specific condition or mode that a finite state machine can be in at any given time
Transition
The change from one state to another caused by an external input
State-Transition Diagram
A diagram showing the behaviour of a Finite State Machine
State-Transition Table
A table showing every state of an FSM, each possible input and the state after the input
Event
An external input that causes a transition from one state to another
Condition
A requirement that must be satisfied for a transition to occur, often shown in square brackets
Initial State
The starting state of an FSM, indicated by an arrow with a black dot
Stopped State
A final or terminal state, indicated by a double circle in diagrams
State Transition Diagram Basics
A Finite State Machine (FSM) is a mathematical model of a machine that can be in one of a fixed set of possible states. One state is changed to another by an external input, this is called a transition. A diagram showing the behaviour of an FSM is called a state-transition diagram.
Purpose of State Transition Diagrams
State-transition diagrams show conditions needed for an event that will cause a transition to occur, and outputs or actions carried out as the result of that transition.
- Visualize complex system behaviour
- Document algorithms clearly
- Identify all possible states and transitions
- Help in system design and testing
Construction Rules
- States are represented as nodes (circles)
- Transitions are represented as interconnecting arrows
- Events are represented as labels on the arrows
- Conditions can be specified in square brackets after the event label
- The initial state is indicated by an arrow with a black dot
- Stopped state is indicated by a double circle
Real-Life Example: Traffic Light System
A simple traffic light is a finite state machine with three states:
• States: RED, AMBER, GREEN
• Transitions: Timer events cause state changes
• Initial State: RED (when system starts)
• This cycles continuously: RED → AMBER → GREEN → AMBER → RED...
Just like in state diagrams, traffic lights have fixed states and predictable transitions based on timer events.
Simple State Diagram Visualization
Interact with this simple FSM. Click on events to trigger state transitions and see how the machine moves between states.
How it works:
- States: S1 (initial), S2, S3 (final)
- Transitions: Input 1 moves from S1→S2, Input 2 moves from S2→S3
- Events: External inputs that trigger transitions
- Final State: S3 is a stopped state (double circle)
Check Your Understanding: State Diagram Basics
1. What is a Finite State Machine (FSM)? [2 marks]
Answer
- [1 mark] A mathematical model of a machine that can be in one of a fixed set of possible states
- [1 mark] One state is changed to another by an external input (transition)
- [Additional] Used to model systems with discrete states and predictable transitions
2. What is the difference between a state and a transition? [2 marks]
Answer
- [1 mark] A state is a specific condition the machine is in at a given time
- [1 mark] A transition is the change from one state to another caused by an external input
- [Additional] States are represented as circles, transitions as arrows between them
3. How is an initial state represented in a state-transition diagram? [1 mark]
Answer
- [1 mark] By an arrow with a black dot pointing to the initial state
- [Additional] This arrow doesn't come from another state - it shows where the system starts
4. What is the purpose of a state-transition diagram? [2 marks]
Answer
- [1 mark] To show conditions needed for events that cause transitions
- [1 mark] To document outputs or actions carried out as the result of transitions
- [Additional] To visualize and document the behaviour of algorithms or systems
5. How are conditions shown in state-transition diagrams? [1 mark]
Answer
- [1 mark] In square brackets after the event label
- [Additional] Example: "Button Press [time > 5s]" means the transition only occurs if button is pressed AND time is greater than 5 seconds
Example: Door Unlocking System
Algorithm for unlocking a door using a three-digit entry code can be represented by a state transition diagram. If door is unlocked with a three-digit entry code, lock can be in four states.
States for 3-Digit Code System
The Four States
- Locked and waiting for the input of the first digit
- Waiting for the input of the second digit
- Waiting for the input of the third digit
- Unlocked (stopped state)
If incorrect digit is input, then door returns to locked state. Algorithm halts when door is unlocked.
State-Transition Table (Code: 259)
| Current State | Event | Next State |
|---|---|---|
| locked | 2 input | waiting for input of 2nd digit |
| locked | not 2 input | locked |
| waiting for input of 2nd digit | 5 input | waiting for input of 3rd digit |
| waiting for input of 2nd digit | not 5 input | locked |
| waiting for input of 3rd digit | 9 input | unlocked and stopped |
| waiting for input of 3rd digit | not 9 input | locked |
Correct code: 2-5-9. Any wrong digit resets to locked state.
Activity 1: Door Lock State Diagram
Draw a state transition diagram for the door unlocking system with code "259". Include all states, transitions, and show what happens with correct and incorrect inputs.
Requirements:
- Show all 4 states with correct notation
- Label transitions with correct digit inputs
- Show transitions for incorrect inputs
- Indicate initial and stopped states properly
Solution:
Key Points:
1. Locked state is initial (black dot arrow)
2. Unlocked is final state (double circle)
3. Correct digits: 2→5→9 moves through states
4. Any wrong digit returns to Locked state
Door Lock Simulation (Code: 259)
Try to unlock the door by entering the correct 3-digit code. Watch how the state changes with each digit input.
Code Entry History
State transitions in this simulation:
- State 1 (Locked): Accepts only digit 2 → moves to Wait 2nd state
- State 2 (Wait 2nd): Accepts only digit 5 → moves to Wait 3rd state
- State 3 (Wait 3rd): Accepts only digit 9 → moves to Unlocked state
- Wrong digit at any state: Returns to Locked state, resets input
- Unlocked: Final state (algorithm halts)
Real-Life Example: Phone PIN Entry
Your phone's PIN entry works exactly like the door lock example:
After too many wrong attempts, the phone might add another state: "Locked for 30 minutes" before returning to the initial locked state.
Check Your Understanding: Door Lock Example
1. How many states are in the 3-digit door lock FSM? [1 mark]
Answer
- [1 mark] 4 states
- [Additional] Locked, Waiting for 2nd digit, Waiting for 3rd digit, Unlocked
2. What happens when an incorrect digit is entered? [2 marks]
Answer
- [1 mark] The door returns to the locked state
- [1 mark] The user must start again from the beginning
- [Additional] This provides security by not giving hints about which digit was wrong
3. From the state-transition table, what is the next state if current state is "waiting for input of 2nd digit" and input is "5"? [1 mark]
Answer
- [1 mark] "waiting for input of 3rd digit"
- [Additional] This is the correct second digit for code 259
4. Why is the "unlocked" state a stopped state? [2 marks]
Answer
- [1 mark] The algorithm halts when the door is unlocked
- [1 mark] No further inputs are processed (door stays unlocked)
- [Additional] Represented by a double circle in the diagram
5. If the code was 4-1-7 instead of 2-5-9, how would the state-transition table change? [2 marks]
Answer
- [1 mark] "2 input" would change to "4 input" in first row
- [1 mark] "5 input" would change to "1 input" in third row, "9 input" to "7 input" in fifth row
- [Additional] The structure remains the same, only the specific digits change
Two's Complement FSM Example
Creating a state-transition diagram for a two's complement FSM. Finite state machine will take as input a positive binary integer, one bit at a time, starting with least significant bit. FSM converts binary integer into two's complement negative equivalent.
Conversion Method
Two's Complement Algorithm
Method to be used is as follows:
- Output the bits input up to and including the first 1
- Output the other bits following this scheme:
- For each 1, output a 0
- For each 0, output a 1
Output: 1 (first 1), 0 (next 1), 0 (next 0), 1 (last 0 flipped)
Result: 1010 (which is -6 in two's complement)
State-Transition Table with Outputs
| Current State | Input Bit | Next State | Output Bit |
|---|---|---|---|
| S1 | 0 | S1 | 0 |
| 1 | S2 | 1 | |
| S2 | 0 | S2 | 1 |
| 1 | S2 | 0 |
- S1: Haven't seen first 1 yet → output 0 for 0, output 1 and move to S2 for 1
- S2: Have seen first 1 → flip bits (1→0, 0→1)
Step-by-Step Example: Convert 0110 (6) to Two's Complement
Step 1: Initial State
Starting in state S1. Process bits from least significant bit (LSB) first: 0, then 1, then 1, then 0.
Step 2: First Bit (0) - Still in S1
According to table: S1, input 0 → stay in S1, output 0. Haven't seen first 1 yet.
Step 3: Second Bit (1) - Move to S2
According to table: S1, input 1 → move to S2, output 1. This is the first 1 encountered.
Step 4: Third Bit (1) - In S2, Flip Bit
According to table: S2, input 1 → stay in S2, output 0. Bit flipped (1 becomes 0).
Step 5: Fourth Bit (0) - In S2, Flip Bit
According to table: S2, input 0 → stay in S2, output 1. Bit flipped (0 becomes 1).
Final Result: 1010 (which is -6 in two's complement 4-bit representation)
Activity 2: Two's Complement Conversion
Convert the binary number 0101 (5 in decimal) to its two's complement equivalent (-5) using the FSM method. Show each step including states, inputs, and outputs.
Given: 0101 (4-bit binary for decimal 5)
- Process bits LSB first: 1, 0, 1, 0
- Use the state-transition table provided
- Show state changes and outputs at each step
- What is the final two's complement result?
Solution:
Step 1: Initial State S1, Input LSB first: 1, 0, 1, 0
Step 2: First bit (1) → Move to S2, Output 1
S1, input 1 → S2, output 1 (first 1 encountered)
Step 3: Second bit (0) → Stay in S2, Output 1 (flipped)
S2, input 0 → S2, output 1 (0 flipped to 1)
Step 4: Third bit (1) → Stay in S2, Output 0 (flipped)
S2, input 1 → S2, output 0 (1 flipped to 0)
Step 5: Fourth bit (0) → Stay in S2, Output 1 (flipped)
S2, input 0 → S2, output 1 (0 flipped to 1)
Final Result:
Input (5): 0101 → Output (-5): 1011
Verification: 1011 in two's complement = -8 + 0 + 2 + 1 = -5 ✓
Two's Complement FSM Simulation
Watch how the FSM converts a binary number to its two's complement. Step through each bit to see state changes and outputs.
Input Binary Number (4-bit)
FSM Rules for Two's Complement:
- State S1 (before first 1): Input 0 → output 0, stay in S1. Input 1 → output 1, move to S2
- State S2 (after first 1): Input 0 → output 1, stay in S2. Input 1 → output 0, stay in S2
- Processing order: Least Significant Bit (LSB) first (rightmost bit)
- Result: Output bits form the two's complement of the input
Real-Life Example: CPU Arithmetic Unit
Inside a CPU, the arithmetic logic unit (ALU) uses FSM-like circuits to perform two's complement operations for subtraction:
The FSM for two's complement can be physically implemented using logic gates in the CPU, allowing fast subtraction using only addition circuits.
Check Your Understanding: Two's Complement FSM
1. In the two's complement FSM, what causes the transition from S1 to S2? [1 mark]
Answer
- [1 mark] Input of 1 (the first 1 encountered)
- [Additional] This marks the point where bit flipping begins
2. What is the output when in state S2 and input is 0? [1 mark]
Answer
- [1 mark] Output 1
- [Additional] Bits are flipped in S2: 0 becomes 1, 1 becomes 0
3. Why does the FSM process bits starting from the LSB? [2 marks]
Answer
- [1 mark] The two's complement algorithm needs to find the first 1 from the right
- [1 mark] Processing LSB first ensures we identify the rightmost 1 correctly
- [Additional] This matches the mathematical definition of two's complement
4. If input is all zeros (0000), what will be the output and final state? [2 marks]
Answer
- [1 mark] Output: 0000 (all zeros)
- [1 mark] Final state: S1 (never transitions to S2 because no 1 is found)
- [Additional] Two's complement of 0 is 0, which is correct
5. How does this FSM relate to the two's complement algorithm steps? [2 marks]
Answer
- [1 mark] S1 corresponds to "output bits up to and including first 1"
- [1 mark] S2 corresponds to "flip remaining bits (1→0, 0→1)"
- [Additional] The FSM implements the algorithm step-by-step
Key Takeaways
- A Finite State Machine (FSM) is a mathematical model with fixed states and transitions
- State-transition diagrams visually represent FSM behaviour using circles (states) and arrows (transitions)
- States are specific conditions the system can be in (e.g., Locked, Unlocked, S1, S2)
- Transitions are changes between states triggered by events/inputs
- Events are external inputs that cause transitions, labelled on arrows
- Conditions can be specified in square brackets after event labels
- The initial state is shown with an arrow from a black dot
- Stopped/final states are shown with double circles
- State-transition tables show every state, possible inputs, and next states
- Example 1: Door lock with 3-digit code has 4 states and resets on wrong digits
- Example 2: Two's complement FSM converts binary numbers using 2 states (S1, S2)
- In two's complement FSM: S1 outputs same bits until first 1, S2 flips bits (1→0, 0→1)
- FSMs process inputs sequentially, one at a time
- State diagrams help document algorithms clearly and identify all possible behaviours
- Real-world applications: security systems, traffic lights, CPU arithmetic, vending machines
- Structure charts decompose problems into sub-tasks, while state diagrams document algorithm behaviour
Question Bank
1. Define a Finite State Machine (FSM) and explain its key components. [4 marks]
Marking Scheme & Answer
- [1 mark] A mathematical model of a machine that can be in one of a fixed set of possible states
- [1 mark] States: Specific conditions the machine can be in
- [1 mark] Transitions: Changes from one state to another caused by external inputs
- [1 mark] Events/Inputs: External stimuli that trigger transitions
- [Additional] Represented visually by state-transition diagrams with circles and arrows
2. Draw and explain the state-transition diagram for a door lock with code 4-3-6. [5 marks]
Marking Scheme & Answer
- [1 mark] 4 states: Locked (initial), Wait 2nd digit, Wait 3rd digit, Unlocked (final/double circle)
- [1 mark] Correct transitions for code 4-3-6: Locked→Wait 2nd on input 4, Wait 2nd→Wait 3rd on input 3, Wait 3rd→Unlocked on input 6
- [1 mark] Self-loop on Locked for inputs not 4
- [1 mark] Transitions back to Locked from Wait 2nd for inputs not 3, from Wait 3rd for inputs not 6
- [1 mark] Proper notation: initial state arrow from black dot, final state as double circle
Key points: Same structure as 2-5-9 example, only digits change. Wrong inputs always return to Locked. Unlocked is terminal state.
3. Complete the state-transition table for a vending machine that accepts only 50p coins and sells items for £1. [6 marks]
States: Idle, Have 50p, Dispense Item
Inputs: Insert 50p, Timeout, Collect Item
Marking Scheme & Answer
| Current State | Event | Next State |
|---|---|---|
| Idle | Insert 50p | Have 50p |
| Have 50p | Insert 50p | Dispense Item |
| Have 50p | Timeout [after 30s] | Idle |
| Dispense Item | Collect Item | Idle |
- [1 mark each] Correct next state for each of the 4 transitions (4 marks)
- [1 mark] Condition [after 30s] on Timeout event
- [1 mark] Logical completeness (covers all state/event combinations)
- [Additional] Idle is initial state, Dispense Item is temporary state before returning to Idle
4. Using the two's complement FSM, convert 1100 (12 in decimal) to its two's complement. Show each step. [5 marks]
Marking Scheme & Answer
- [1 mark] Step 1: S1, input 0 → S1, output 0
- [1 mark] Step 2: S1, input 0 → S1, output 0
- [1 mark] Step 3: S1, input 1 → S2, output 1 (first 1)
- [1 mark] Step 4: S2, input 1 → S2, output 0 (flip)
- [1 mark] Output: 0 0 1 0 → reversed: 0100 (4 in two's complement = -12)
Verification: 1100 = 12 → Two's complement should be -12 = 0100 in 4-bit (since 0100 = 4, and -12 mod 16 = 4) ✓
5. Explain the difference between a state-transition diagram and a structure chart. [4 marks]
Marking Scheme & Answer
| Aspect | State-Transition Diagram | Structure Chart |
|---|---|---|
| Purpose | Document algorithm behaviour and state changes | Decompose problem into sub-tasks/modules |
| Focus | States, transitions, events, conditions | Modules, procedures, functions, parameters |
| Elements | Circles (states), arrows (transitions), labels (events) | Boxes (modules), arrows (calls), labels (parameters) |
| Usage | Model systems with discrete states (FSMs) | Show program structure and hierarchy |
Key difference: State diagrams show how system behaves over time with state changes, while structure charts show how program is organized into components.
6. Create a state-transition diagram for a traffic light pedestrian crossing system. [6 marks]
States: Green (cars), Amber, Red (cars), Red+Green (pedestrians), Red+Amber (pedestrians)
Events: Timer, Button Press
Marking Scheme & Answer
- [1 mark] Initial state: Green (cars) - normal traffic flow
- [1 mark] Green → Amber on Timer (normal cycle)
- [1 mark] Amber → Red on Timer (normal cycle)
- [1 mark] Red → Red+Green (pedestrians) when Button Press detected during Red state
- [1 mark] Red+Green → Red+Amber on Timer (pedestrian warning)
- [1 mark] Red+Amber → Green (cars) on Timer (return to normal)
- [Additional] Without button press, Red → Green on Timer (skips pedestrian phase)
Key logic: Pedestrian phase only triggered if button pressed during Red state. Timer events control all automatic transitions.
7. What is the purpose of conditions in square brackets in state diagrams? Give an example. [3 marks]
Marking Scheme & Answer
- [1 mark] Conditions specify additional requirements that must be met for a transition to occur
- [1 mark] They are shown in square brackets after the event label
- [1 mark] Example: "Button Press [time > 5s]" means transition only occurs if button is pressed AND system has been in current state for more than 5 seconds
- [Additional] Allows for more complex transition logic beyond simple event triggering
8. How would the two's complement FSM change if we processed bits MSB first instead of LSB? [3 marks]
Marking Scheme & Answer
- [1 mark] It wouldn't work correctly for the two's complement algorithm
- [1 mark] The algorithm needs to find the rightmost 1 (LSB-first processing)
- [1 mark] MSB-first would flip bits from the wrong starting point, giving incorrect results
- [Additional] Example: For 0110, MSB-first would flip all bits after first 0, giving wrong answer
9. Describe a real-world system (not mentioned in notes) that could be modelled with an FSM. [4 marks]
Marking Scheme & Answer
- [1 mark] Elevator system: States: Idle, Moving Up, Moving Down, Doors Open, Doors Closing
- [1 mark] Events: Floor button pressed, Door open/close button, Weight sensor, Timer
- [1 mark] Transitions: Idle → Moving Up when upper floor button pressed, Moving Up → Doors Open when target floor reached, etc.
- [1 mark] Conditions: Doors Open → Doors Closing [timer > 10s AND no obstruction]
- [Additional] Other examples: Microwave oven, Washing machine, ATM, Game character AI
10. Why are state-transition diagrams useful for documenting algorithms? [3 marks]
Marking Scheme & Answer
- [1 mark] Visual clarity: Easy to see all possible states and transitions at a glance
- [1 mark] Completeness check: Helps identify missing states or transition scenarios
- [1 mark] Communication: Clear way to explain algorithm behaviour to others (developers, clients)
- [Additional] Also useful for testing (check all paths), implementation (guides coding), and debugging