Computer Science 9608
Paper 4: Sec 4.2.3)State-transition diagrams
with Majid Tahir
Syllabus Content:
4.2 Algorithm design methods
4.2.3 State-transition diagrams
use state-transition diagrams to document an algorithm
use state-transition diagrams to show the behaviour of an object
4.2.3: State- transition diagrams:
A computer system can be seen as a finite state machine (FSM). An FSM has a start state. An
input to the FSM produces a transformation from one state to another state.
The information about the states of an FSM can be presented in a state-transition table.
Table shows an example FSM represented as a state-transition table If the FSM is in state Sl, an
input of a causes no change of state.
If the FSM is in state S1, an input of b transforms
S1 to S2.
If the FSM is in state S2, an input of b causes no
change of state.
If the FSM is in state S2, an input of a transforms
S2 to S1.
A state-transition diagram can be used to describe the behaviour of Table 24.05 State-transition
table an FSM.
Figure STD shows the start state as S1 (denoted by• ). If the FSM has a final state
(also known as the halting state), this is shown by a double-circled state (S1 in the example).
Figure STD
www.majidtahir.com Contact: +923004003666 Email: majidtahir61@gmail.com
1
Computer Science 9608
Paper 4: Sec 4.2.3)State-transition diagrams
with Majid Tahir
If an input causes an output this is shown by a vertical bar, For example, if the current state is
S1, an input of b produces output c and transforms the FSM to state S2.
Figure State-transition diagram with outputs
Creating a state-transition diagram for an intruder detection system
A program is required that simulates the behaviour of an intruder detection system.
Description of the system: The system has a battery power supply. The system is activated when
the start button is pressed. Pressing the start button when the system is active has no effect. To
de-activate the system, the operator must enter a PIN. The system goes into alert mode when a
sensor is activated. The system will stay in alert mode for two minutes. If the system has not
been de-activated within two minutes an alarm bell will ring.
We can complete a state-transition table (Table) using the information from the system
description.
www.majidtahir.com Contact: +923004003666 Email: majidtahir61@gmail.com
2
Computer Science 9608
Paper 4: Sec 4.2.3)State-transition diagrams
with Majid Tahir
The start state is 'System inactive'. We can draw a state-transition diagram (Figure 24.07) from
the information in Table
Past Paper Questions:
9608/41/M/J/15
1/- A turnstile is a gate which is in a locked state. To open it and pass through, a
customer inserts a coin into a slot on the turnstile. The turnstile then unlocks and allows
the customer to push the turnstile and pass through the gate.
After the customer has passed through, the turnstile locks again. If a customer pushes
the turnstile while it is in the locked state, it will remain locked until another coin is
inserted.
The turnstile has two possible states: locked and unlocked. The transition from one
state to another is as shown in the table below.
www.majidtahir.com Contact: +923004003666 Email: majidtahir61@gmail.com
3
Computer Science 9608
Paper 4: Sec 4.2.3)State-transition diagrams
with Majid Tahir
(9608/43/M/J/15)
Q2/ - A petrol filling station has a single self-service petrol pump.
A customer can use the petrol pump when it is ready to dispense petrol. The pump is in
use when the customer takes the nozzle from a holster on the pump. The pump
dispenses petrol while the customer presses the trigger on the nozzle. When the
customer replaces the nozzle into the holster, the pump is out of use. The cashier must
press a reset button to make the pump ready for the next customer to use.
The petrol pump’s four possible states and the transition from one state to another are
as shown in the table below.
www.majidtahir.com Contact: +923004003666 Email: majidtahir61@gmail.com
4
Computer Science 9608
Paper 4: Sec 4.2.3)State-transition diagrams
with Majid Tahir
Complete the state transition diagram for the petrol pump:
www.majidtahir.com Contact: +923004003666 Email: majidtahir61@gmail.com
5
Computer Science 9608
Paper 4: Sec 4.2.3)State-transition diagrams
with Majid Tahir
Answers
9608/41/M/J/15
www.majidtahir.com Contact: +923004003666 Email: majidtahir61@gmail.com
6
Computer Science 9608
Paper 4: Sec 4.2.3)State-transition diagrams
with Majid Tahir
(9608/43/M/J/15)
Refrences:
AS & A level Course Book by Sylvia Langfield & Dave Duddell
A level 9608 Pastpaers
www.majidtahir.com Contact: +923004003666 Email: majidtahir61@gmail.com
7
