Finite Models
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 1
Learning objectives
• Learn how to model finite state behavior with finite state machines
• Learn how to model specifications with finite state machines
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 2
Finite state machines
• A Finite State Machine (FSM) is defined by a finite set of states (nodes), a transition relation, the alphabet, and the initial state(s)
– Set of states S
– Initial state(s) in S
– Set of actions A – or inputs/outputs
• If an FSM receives inputs and outputs some results – called a
transducer
• Iftherearenooutputs–thenjustinputsorjustactions
– Transition relation T: S x A → S
– If there are inputs and outputs, then T: S x I → SxO
• FSM represent the specification or the
functional properties of the system
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 3
Example – a Coffee Vending Machine
• A simple version:
– a machine that only dispenses coffee and only takes 50p (no change, one coin)
• A more complex version:
– a machine that takes 20p and 10p coins (but no change)
• An even more complex version: – a machine that gives change
• The final version:
– a machine that dispenses several types of coffee, takes 20p and 10p coins, and gives change
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 4
From an informal specification…
Maintenance: The Maintenance function records the history of items undergoing maintenance.
If the product is covered by warranty or maintenance contract, maintenance can be requested either by calling the maintenance toll free number, or through the web site, or by bringing the item to a designated maintenance station.
If the maintenance is requested by phone or web site and the customer is a US or EU resident, the item is picked up at the customer site, otherwise, the customer shall ship the item with an express courier.
If the maintenance contract number provided by the customer is not valid, the item follows the procedure for items not covered by warranty.
If the product is not covered by warranty or maintenance contract, maintenance can be requested only by bringing the item to a maintenance station. The maintenance station informs the customer of the estimated costs for repair. Maintenance starts only when the customer accepts the estimate.
If the customer does not accept the estimate, the product is returned to the customer.
Small problems can be repaired directly at the maintenance station. If the maintenance station cannot solve the problem, the product is sent to the maintenance regional headquarters (if in US or EU) or to the maintenance main headquarters (otherwise).
If the maintenance regional headquarters cannot solve the problem, the product is sent to the maintenance main headquarters.
Maintenance is suspended if some components are not available. Once repaired, the product is returned to the customer.
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 5
From an informal specification…
Maintenance: The Maintenance function records the history of items undergoing maintenance.
If the product is covered by warranty or maintenance contract, maintenance can be
requested either by calling the maintenance toll free number, or through the web site, or
by bringing the item to a designated maintenance station.
step …
If the maintenance is requested by phone or web site and the customer is a US or EU resident, the item is picked up at the customer site, otherwise, the customer shall ship the item with an express courier.
the procedure for items not covered by warranty.
If the product is not covered by warranty or maintenance contract, maintenance can be requested only by bringing the item to a maintenance station. The maintenance station informs the customer of the estimated costs for repair. Maintenance starts only when the customer accepts the estimate.
If the maintenance contract number provided by the customer is not valid, the item follows
Small problems can be repaired directly at the maintenance station. If the maintenance station cannot solve the problem, the product is sent to the maintenance regional headquarters (if in US or EU) or to the maintenance main headquarters (otherwise).
If the maintenance regional headquarters cannot solve the problem, the product is sent to the maintenance main headquarters.
Maintenance is suspended if some components are not available. Once repaired, the product is returned to the customer.
Multiple choices in the first
… determine the possibilities
for the next step …
If the customer does not accept the estimate, the product is returned to the customer.
… and so on …
(c) 2007 Mauro Pezzè & Michal Young Ch 14, slide 6
0
NO Maintenance
1
Wait for returning
2 Maintenance (no warranty )
3
return
Wait for pick up
…to a finite state machine…
Repaired
4
5
component arrives (a)
lackcomponent (b)
component arrives (b)
Wait for acceptance
Repair estimate (maintenance
station)
6
accept
repair completed
7
8
Wait for component
Repair (regional headquarters )
unable to repair
(not US or EU resident )
component arrives (c)
9 Repair (main
(c) 2007 Mauro Pezzè & Michal Young
headquarters )
Ch 14, slide 7
pickup
pickup
est ima te c o s ts
requestat maintenance station or by express courier (contract number)
request a t maintenance station (n o warranty)
request
by phone or web [US or EU resident] (contract number)
reject estimate
inv alid c o nt r a ct number
un able to repair (US or EUresident)
successful repair
lackcomponent(a)
successful repair
unable to repair
lackcomponent (c)
Example: microwave
• Naturallanguagerequirementsforamicrowaverequirethe following:
– When the start button is pushed and the door is closed, the microwave heats the food inside for 1 minute.
– Pushing the start button while heating has no effect.
– Pushing the start button if the door is open has no effect.
– Pushing the start button when there is no food inside has no effect.
– After heating, the food is hot (you can assume this is the end of the heating process).
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 8
FSM for the microwave
States are denoted with four letters: O/C (door open/closed), F/N (food/no food inside), H/S (heating/shut down – not heating), H/L (food hot/cold) – the fourth letter is added only when the second letter if F and the third is S (assuming the other states are unreachable). Not all actions are enabled at all states.
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 9
Using Models to Reason about System Properties
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 10
Summary
• FSM can be built before software to document intended behaviour
• FSM are used to testing that is not based on the code
(c) 2007 Mauro Pezzè & Michal Young Ch 5, slide 11
Home reading
• Chapter 5 of the book Software Testing and Analysis, by Mauro Pezze and Michal Young
– Finite Models (the part on FSM)
(c) 2007 Mauro Pezzè & Michal Young Ch 1, slide 12