Chapter 12.2: Program Design

Structure Charts & State-Transition Diagrams

9618 AS Computer Science

📚 Learning Objectives

Use a structure chart to decompose a problem into sub-tasks
Express parameters passed between modules/procedures/functions
Describe the purpose of a structure chart
Construct a structure chart for a given problem
Show understanding of the purpose of state-transition diagrams to document an algorithm
Construct state-transition diagrams for given problems
Complete state-transition tables from given diagrams

📋 Prior Knowledge Required

Understanding of top-down design and stepwise refinement
Knowledge of procedures and functions in programming
Understanding of parameters and return values
Basic knowledge of algorithm design using pseudocode
Understanding of selection (IF statements) and iteration (loops)

🌟 Did You Know?

Structure charts and state-transition diagrams are essential modelling tools used in the design stage of program development. They help programmers visualise how modules are interrelated and how systems move between different states based on inputs. These tools focus on WHAT the program does, not HOW it does it!

1. Structure Charts

A structure chart is a modelling tool used in the design stage of program development. It helps to decompose a problem into smaller, manageable sub-tasks, representing each as a module.

📖 Definition: Structure Chart

A structure chart is a modelling tool used in program design to decompose a problem into a set of sub-tasks. The structure chart shows the hierarchy of the different modules and how they connect and interact with each other.

1.1 Purpose of Structure Charts

Key Purpose	Description
Decomposition	Breaks down complex problems into smaller, manageable sub-tasks
Visualise Relationships	Shows how modules are interrelated and interface with each other
Parameter Passing	Shows what data is passed between modules (parameters and return values)
Interface Design	Shows the interface between modules (the variables/parameters)
Documentation	Provides clear documentation for program design

⚠️ Important

Structure charts focus on WHAT the program does, not HOW it does it. They are used in the design stage to plan the program structure before writing actual code.

1.2 Key Features of Structure Charts

Feature	Explanation
Top-down Design	Chart starts with main program and breaks into sub-modules
Decomposition	Each module represents a specific task or function
Module Boxes	Each module is shown as a box
Vertical Lines	Show control flow – which module calls which
Parameter Arrows	Arrows pointing into modules show data being passed in or returned
Stepwise Refinement	Each level adds more detail to the task above

💡 Exam Tip

Remember: Each level of the structure chart is a refinement of the level above. The top level shows the main task, and each subsequent level breaks down the task into more detail.

2. Structure Chart Symbols

2.1 Basic Symbols

Symbol	Name	Description
Rectangle Box	Process/Module/Subroutine	Indicates the module/subroutine name
Vertical Line	Call Line	Shows the program flow path between modules (how they connect)
Diamond Shape	Selection	Shows where program may branch off onto different call lines (condition)
Semi-circular Arrow	Repetition	Indicates a process may be repeated (loop)

2.2 Data Flow Arrows

Arrow Type	Meaning	Description
Data Flow Arrow	Data being passed	Used to indicate where data is being passed between modules. Can be parameters passed to modules OR return values
Control Flow Arrow	Control signal/flag	Used to indicate where data passed is used to control the flow of the program. Usually a True/False flag passed as a return value
Double-headed Arrow	Updated variable	Shows that variable value is updated within the module
Solid Round End Arrow	Flag (Boolean)	Shows that value transferred is a flag (a Boolean value)

🧠 Memory Trick

Diamond = Decision - A diamond shape looks like a decision point where you can go different ways.

Semi-circle = Loop - The curved arrow going back reminds you of cycling/looping back to repeat.

Round end = Ready/Flag - The solid round end indicates a Boolean flag (True/False).

3. Structure Chart Examples

3.1 Temperature Conversion Example

A simple structure chart for converting a temperature from Fahrenheit to Celsius. The top level shows the name for the whole task that is refined into three sub-tasks or modules shown on the next level.

3.2 Calculate Average Example

Structure chart for a module that calculates the average of two numbers. Input numbers (parameters Number1 and Number2) are passed into the 'Calculate Average' sub-task and then the Average parameter is passed into the 'OUTPUT Average' sub-task.

📝 Key Points About This Example

Top-level box is name of the module, refined into three sub-tasks of Level 1
Arrows show how parameters are passed between modules
This parameter passing is known as the 'interface'
Each module can be developed and tested independently

4. Selection and Repetition in Structure Charts

4.1 Selection (Diamond Shape)

Structure charts can show selection using a diamond-shaped box to show a condition that could be true or false.

The temperature conversion task can be extended to either convert from Fahrenheit to Celsius OR Celsius to Fahrenheit:

4.2 Repetition (Semi-circular Arrow)

Structure charts can show repetition using a labelled semi-circular arrow above the modules to be repeated.

The temperature conversion task can be extended to repeat until the number 999 is input:

💡 Exam Tip

When drawing structure charts:

Selection: Use a diamond shape with branches for each condition
Repetition: Draw a semi-circular arrow over the modules to be repeated, with a label describing the loop condition

5. Complete Structure Chart Example

5.1 Sphere Volume/Surface Area Calculator

Draw a structure chart to input the radius of a sphere, calculate and output either the volume or surface area. The algorithm should repeat until a radius of zero is entered.

📝 Deriving Pseudocode from Structure Chart

Once a structure chart has been completed, it can be used to derive a pseudocode algorithm:

First, create an identifier table from the parameters shown
Then identify any functions or procedures that could be used
Finally, write the pseudocode based on the structure chart hierarchy

Identifier Table

DECLARE radius : REAL
DECLARE answer : REAL
DECLARE choice : STRING

6. State-Transition Diagrams

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.

📖 Definition: State-Transition Diagram

A diagram showing the behaviour of an FSM is called a state-transition diagram. It shows how a system moves between different states based on inputs.

State-transition diagrams show:

The conditions needed for an event that will cause a transition to occur
The outputs or actions carried out as the result of that transition

6.1 Key Elements

Element	Description
State	Circle labelled with a name (e.g., S1, S2) showing a situation the system can be in
Initial State	Starting point, indicated by an arrow with a black dot pointing to it
Transition	Arrow from one state to another, labelled with input and output
Input	Event or data that causes a transition (e.g., Button-Y pressed)
Output	Action or signal produced by a transition (e.g., Output-A)
Next State	The state the system moves into after the transition
Stopped State	Indicated by a double circle (halting state)

6.2 Reading Labels on Transitions

📝 How to Read Transition Labels

Labels are often written as Input | Output
If no output is produced, "none" may be written
Example: Button-Y | Output-B means pressing Button-Y in the current state produces Output-B and causes a transition to the next state

💡 Exam Tip

Always identify the initial state before tracing through a state-transition diagram. Look for the arrow with a black dot pointing to a state - that's where you start!

7. Constructing State-Transition Diagrams

7.1 Construction Rules

📝 How to Construct State-Transition Diagrams

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
A stopped/halted state is indicated by a double circle

7.2 Example: Door Lock with Entry Code

Algorithm for unlocking a door using a three-digit entry code (259). If the door is unlocked with the correct three-digit code, the lock can be in four states:

📖 Possible States for Door Lock

Locked - waiting for the input of the first digit
Got2 - waiting for the input of the second digit (after correct first digit)
Got25 - waiting for the input of the third digit (after correct first two digits)
Unlocked - door is unlocked (halt state)

Important: If an incorrect digit is input at any point, the door returns to the Locked state.

⚠️ Important Note

The double circle around the Unlocked state indicates that the lock halts in this state. The algorithm stops when the door is unlocked.

8. State-Transition Tables

A state-transition table shows every state of a finite state machine (FSM), each possible input, and the state after the input.

8.1 Table Structure

Column	Description
Current State	The state the system is currently in
Input	The event or data that triggers a transition
Output	The action or signal produced (if any)
Next State	The state the system moves to after the transition

8.2 State-Transition Table for Door Lock (Code: 259)

Current State	Input	Output	Next State
Locked	2	none	Got2
Locked	0, 1, 3, 4, 5, 6, 7, 8, 9	none	Locked
Got2	5	none	Got25
Got2	0, 1, 2, 3, 4, 6, 7, 8, 9	none	Locked
Got25	9	Unlock	Unlocked
Got25	0, 1, 2, 3, 4, 5, 6, 7, 8	none	Locked

📝 How to Complete State-Transition Tables

Start with the initial state as the current state
For each possible input, trace the arrow to find the next state
Note the output (if any) shown on the transition arrow
Continue until all states and inputs are covered

💡 Examiner Tips and Tricks

Always identify the initial state before tracing
Highlight or mark inputs and outputs on your diagram to avoid missing any
For tables, keep the order consistent: Input → Output → Next state
Use arrows systematically, avoid guessing paths
Remember: more than one sequence can sometimes reach the same state

9. Two's Complement FSM Example

A finite state machine can convert a positive binary integer into its two's complement negative equivalent. The FSM takes input one bit at a time, starting with the least significant bit.

9.1 Two's Complement Method

📝 Conversion Rules

Output the bits input up to and including the first 1
For all remaining bits:
- For each 1, output a 0
- For each 0, output a 1

9.2 Example Conversion

Example: Convert binary 00011010 (26 in decimal) to two's complement

Input bits (LSB first): 0 → 1 → 0 → 1 → 1 → 0 → 0 → 0

Trace through FSM:

Input 0: Stay in S1, Output 0
Input 1: Move to S2, Output 1 (first 1 found!)
Input 0: Stay in S2, Output 1 (flipped)
Input 1: Stay in S2, Output 0 (flipped)
Input 1: Stay in S2, Output 0 (flipped)
Input 0: Stay in S2, Output 1 (flipped)
Input 0: Stay in S2, Output 1 (flipped)
Input 0: Stay in S2, Output 1 (flipped)

Output: 0 → 1 → 1 → 0 → 0 → 1 → 1 → 1
Result: 11100110 (which is -26 in two's complement)

10. From Structure Chart to Pseudocode

Once a structure chart has been completed, it can be used to derive a pseudocode algorithm. Here's a complete example of a login system.

10.1 Login System Example

A program that asks a user to enter their username and password, checks if the password matches the stored password, and uses a counter to track attempts. After three failed attempts, access is denied.

Identifier	Data Type	Description
Username	STRING	Stores the username entered by the user
Password	STRING	Stores the password entered by the user
StoredPass	STRING	The correct password stored in the system
NoAttempts	INTEGER	Counts the number of failed login attempts
LoginSuccess	BOOLEAN	Indicates whether the login was successful

10.2 Module Identification

Module	Type	Purpose
GetCredentials	PROCEDURE	Asks the user to input username and password
CheckPassword	FUNCTION	Compares input password with stored password and returns TRUE/FALSE
ShowAccessMessage	PROCEDURE	Displays success or failure message

Pseudocode Implementation

DECLARE Username : STRING
DECLARE Password : STRING
DECLARE StoredPass : STRING
DECLARE NoAttempts : INTEGER
DECLARE LoginSuccess : BOOLEAN

StoredPass ← "admin123"
NoAttempts ← 0
LoginSuccess ← FALSE

PROCEDURE GetCredentials()
    OUTPUT "Enter username: "
    INPUT Username
    OUTPUT "Enter password: "
    INPUT Password
ENDPROCEDURE

FUNCTION CheckPassword(P : STRING) RETURNS BOOLEAN
    IF P = StoredPass THEN
        RETURN TRUE
    ELSE
        RETURN FALSE
    ENDIF
ENDFUNCTION

PROCEDURE ShowAccessMessage(Success : BOOLEAN)
    IF Success = TRUE THEN
        OUTPUT "Login successful"
    ELSE
        OUTPUT "Access denied"
    ENDIF
ENDPROCEDURE

// Main program
WHILE NoAttempts < 3 AND LoginSuccess = FALSE
    CALL GetCredentials()
    LoginSuccess ← CheckPassword(Password)
    IF LoginSuccess = FALSE THEN
        OUTPUT "Incorrect password"
        NoAttempts ← NoAttempts + 1
    ENDIF
ENDWHILE

CALL ShowAccessMessage(LoginSuccess)

11. Exam-Style Questions

1. Describe the purpose of a structure chart in program design. [4 marks]

Answer:

A structure chart is a modelling tool used in the design stage of program development
It helps to decompose a problem into smaller, manageable sub-tasks
It shows the hierarchy of different modules and how they connect and interact
It shows the interface between modules (parameters and return values)
It focuses on WHAT the program does, not HOW it does it
It allows programmers to visualise how modules are interrelated

Additional points for deeper understanding:

Structure charts help with stepwise refinement
They can show selection (diamond) and repetition (semi-circular arrow)

2. Explain the difference between a data flow arrow and a control flow arrow in a structure chart. [4 marks]

Answer:

Data flow arrow: Shows data being passed between modules in the form of parameters or return values
Control flow arrow: Shows data used to control the flow of the program (usually a Boolean flag)
Data flow arrows typically show values like numbers, strings, or other data types
Control flow arrows typically show True/False flags that determine program flow
A control flow arrow has a solid round end to indicate a flag/Boolean value

Additional points for deeper understanding:

Double-headed arrows show variables that are updated within a module
The direction of the arrow indicates which module receives the data

3. Draw a structure chart for a program that inputs two numbers, calculates their sum and product, and outputs both results. [6 marks]

Answer Structure Chart:

Top level: CalculateResults (main module)
Level 1: Three sub-modules connected vertically:
- InputNumbers - inputs two numbers (N1, N2)
- Calculations - calculates sum and product
- OutputResults - outputs sum and product
Data flow arrows showing N1, N2 passed to Calculations
Data flow arrows showing Sum, Product passed to OutputResults
Correct use of module boxes (rectangles)
Vertical lines showing control flow between modules

Marks awarded for: main module (1), sub-modules (2), data flow arrows (2), correct connections (1)

4. What is a Finite State Machine (FSM)? Explain how state-transition diagrams are used to model FSMs. [5 marks]

Answer:

An 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, called a transition
State-transition diagrams show states as circles (nodes)
Transitions are shown as interconnecting arrows between states
The initial state is indicated by an arrow with a black dot
A stopped/halted state is shown with a double circle
Transition arrows are labelled with Input | Output

Additional points for deeper understanding:

FSMs are widely used in computing for modeling system behavior
Conditions can be specified in square brackets after event labels

5. Complete the state-transition table for the following state-transition diagram. The diagram shows states S1, S2, S3, S4. Transitions: S1→S2 (Input-A, none), S2→S3 (Input-B, Output-X), S3→S4 (Input-A, Output-Y), S1→S3 (Input-B, none). [4 marks]

Answer:

Current State	Input	Output	Next State
S1	Input-A	none	S2
S1	Input-B	none	S3
S2	Input-B	Output-X	S3
S3	Input-A	Output-Y	S4

One mark for each correct row

11. Exam-Style Questions (Continued)

6. A door lock has an entry code of 367. Draw a state-transition diagram showing the states and transitions for this lock. Include transitions for incorrect digits. [6 marks]

Answer:

Four states: Locked, Got3, Got36, Unlocked
Initial state indicator: Black dot with arrow to Locked state
Correct sequence: Locked → Got3 (digit 3) → Got36 (digit 6) → Unlocked (digit 7)
Unlocked state: Double circle (halted state)
Incorrect digit transitions: From each state back to Locked
Output: "Unlock" on transition to Unlocked state

Additional points for deeper understanding:

Self-loop on Locked for digits 0,1,2,4,5,6,7,8,9
Transitions from Got3 back to Locked for incorrect digits
Transitions from Got36 back to Locked for incorrect digits

7. Explain how selection and repetition are represented in structure charts. Give an example of when each would be used. [6 marks]

Answer:

Selection:

Represented by a diamond-shaped box
Shows where program may branch onto different call lines
Contains a condition that could be true or false
Example: Choosing between converting Fahrenheit to Celsius OR Celsius to Fahrenheit

Repetition:

Represented by a semi-circular arrow
Placed above the modules to be repeated
Labelled with the loop condition
Example: Repeating temperature conversion until user enters 999 to stop

Marks: 3 for selection (symbol, description, example), 3 for repetition (symbol, description, example)

8. A two's complement FSM converts a positive binary number to its negative equivalent. Describe how this FSM works, including the states and transitions. [5 marks]

Answer:

The FSM has two states: S1 (Start/Copy) and S2 (Flip)
Input is processed LSB first (least significant bit first)
In S1: Copy bits as they are until the first 1 is encountered
- Input 0 → Output 0, stay in S1
- Input 1 → Output 1, move to S2
In S2: Flip all remaining bits
- Input 0 → Output 1, stay in S2
- Input 1 → Output 0, stay in S2
This follows the two's complement rule: copy up to and including the first 1, then flip all remaining bits

Additional points for deeper understanding:

The initial state is S1 (indicated by black dot arrow)
There is no halted state - the FSM processes all input bits

9. Describe the process of deriving pseudocode from a structure chart. [5 marks]

Answer:

First, create an identifier table from the parameters shown in the structure chart
Identify any functions or procedures that could be used based on the modules
Determine the data types for each identifier
Write the pseudocode for each module/procedure/function
Implement selection using IF statements (from diamond shapes)
Implement repetition using WHILE or REPEAT loops (from semi-circular arrows)
Write the main program that calls the modules in the correct order

Additional points for deeper understanding:

Use parameters shown by data flow arrows as procedure/function arguments
Use return values shown by arrows pointing away from modules

10. A state-transition diagram has states S1, S2, S3, S4, S5. S1 is the initial state. Transitions are: S1→S3 (Input-A, none), S1→S2 (Input-B, none), S2→S5 (Input-B, none), S3→S2 (Input-B, Output-W), S3→S3 (Input-A, Output-W), S5→S2 (Input-B, none), S5→S4 (Input-A, Output-X). Identify the input sequence that causes the minimum number of state changes to reach S4 from S1. [4 marks]

Answer:

Starting at S1
Path analysis:
- S1 → S2 (Input-B) → S5 (Input-B) → S4 (Input-A) = 3 transitions
- S1 → S3 (Input-A) → S2 (Input-B) → S5 (Input-B) → S4 (Input-A) = 4 transitions
Minimum path: S1 → S2 → S5 → S4
Input sequence: Input-B, Input-B, Input-A

Additional points for deeper understanding:

This requires only 3 state changes to reach S4
The output produced is Output-X on the final transition
Following the S3 path would require more transitions

12. Glossary

📖 Key Terms and Definitions

Structure Chart → A modelling tool used in program design to decompose a problem into a set of sub-tasks and show the hierarchy of modules.

Module → A self-contained unit of code that performs a specific task, represented as a box in a structure chart.

Decomposition → The process of breaking down a complex problem into smaller, manageable sub-tasks.

Parameter → A value passed to a module/procedure/function, shown by arrows in a structure chart.

Interface → The connection between modules, defined by the parameters passed between them.

Stepwise Refinement → The process of adding more detail to each level of a structure chart, with each level being a refinement of the level above.

Selection → A program structure where different paths are taken based on a condition, represented by a diamond shape in structure charts.

Repetition → A program structure where a set of statements is repeated, represented by a semi-circular arrow in structure charts.

Finite State Machine (FSM) → A mathematical model of a machine that can be in one of a fixed set of possible states.

State → A condition or situation of a system, represented as a circle in state-transition diagrams.

Transition → The movement from one state to another caused by an external input.

State-Transition Diagram → A diagram showing the behaviour of an FSM, including states, transitions, inputs, and outputs.

Initial State → The starting state of an FSM, indicated by an arrow with a black dot.

Halted/Stopped State → A state where the FSM stops, indicated by a double circle.

State-Transition Table → A table showing every state, each possible input, output, and the next state.

Data Flow Arrow → An arrow showing data being passed between modules in a structure chart.

Control Flow Arrow → An arrow showing a Boolean flag that controls program flow.

Call Line → A vertical line in a structure chart showing which module calls which.

13. Exam Success Tips

💡 Structure Chart Tips

Start at the top: Always begin with the main program module at the top level
One task per module: Each box should represent one specific task
Label all arrows: Every data flow arrow should be labelled with the parameter name
Diamond for decisions: Use diamond shapes for selection/conditions
Arc for loops: Use semi-circular arrows for repetition with a clear label
Check interfaces: Ensure parameters passed match between modules

💡 State-Transition Diagram Tips

Find the initial state: Look for the black dot arrow - that's where you start
Label format: Use Input | Output format on transition arrows
Double circle = halt: States with double circles are stopped/halted states
Trace systematically: Follow arrows carefully when completing tables
Check all inputs: Make sure all possible inputs from each state are covered
None for no output: Write "none" if there's no output on a transition

❌ Common Mistakes to Avoid

Forgetting the initial state marker: Always include the black dot arrow pointing to the start state
Missing halted state: Double circle for stopped states is often forgotten
Wrong arrow direction: Data flow arrows point TO the module receiving the data
Incomplete state-transition tables: Missing transitions for some inputs
Not showing all incorrect inputs: In door lock examples, show what happens with wrong digits
Confusing data and control flow: Data flow = values, Control flow = Boolean flags
Missing parameter labels: All data flow arrows need parameter names

🧠 Memory Tricks

Diamond = Decision: A diamond has multiple points - like multiple paths in a decision
Arc = Around again: The semi-circular arrow goes "around" to repeat
Double circle = Done: Two circles means the FSM is done/halted
Black dot = Begin: The black dot shows where to begin
Round end = Ready (Boolean): Solid round end indicates a Boolean flag

13. Exam Success Tips (Continued)

💡 Answer Structure Tips

For "describe" questions: Give step-by-step details of how something works
For "explain" questions: Give reasons WHY something happens or differs
For "draw" questions: Use correct symbols and label all elements clearly
For "complete" questions: Follow the order given, check row by row
Mark allocations give hints: [4 marks] = 4 distinct points needed

⚠️ Key Differences to Remember

Structure Chart	State-Transition Diagram
Shows module hierarchy	Shows system states and transitions
Focuses on WHAT the program does	Shows HOW the system behaves
Used for decomposition	Used for modelling FSMs
Shows parameter passing	Shows input/output on transitions
Diamond = selection	Circle = state
Semi-circle = repetition	Double circle = halted state

🌟 Quick Reference: Symbol Summary

Symbol	Structure Chart Meaning	State Diagram Meaning
Rectangle	Module/Process	—
Circle	—	State
Diamond	Selection/Condition	—
Double Circle	—	Halted State
Semi-circular Arrow	Repetition	—
Arrow with Black Dot	—	Initial State
Arrow (pointed)	Data/Control Flow	Transition

14. Key Takeaways

📌 Summary Points

Structure Charts

Purpose: Decompose problems into sub-tasks and show module hierarchy
Focus: WHAT the program does, not HOW
Key symbols: Rectangle (module), Diamond (selection), Semi-circle (repetition)
Arrows: Data flow (parameters), Control flow (Boolean flags)
Each level: A refinement of the level above (stepwise refinement)
Can derive: Pseudocode from completed structure charts

State-Transition Diagrams

Purpose: Model Finite State Machines and document algorithm behaviour
States: Represented by circles (nodes)
Transitions: Arrows between states, labelled with Input | Output
Initial state: Indicated by arrow with black dot
Halted state: Indicated by double circle
Tables: Show Current State, Input, Output, Next State

Two's Complement FSM

Purpose: Convert positive binary to negative equivalent
Input: LSB first (least significant bit)
S1 (Copy): Output bits as-is until first 1
S2 (Flip): Invert remaining bits (0→1, 1→0)