Extended State Machines
CS 447– Wireless Embedded Systems
Outline
• Motivation
• Extended state machine
• Example
1
January 25, 2018
Motivation
Notation for FSM gets unwieldy when number of states large
• E.g., garage counter
• M is small, easy to draw
• M is large, can be cumbersome
2
January 25, 2018
Motivation
Extended state machine solves this problem
• Augments FSM model w/ variables
3
January 25, 2018
Outline
• Motivation
• Extended state machine
• Example
4
January 25, 2018
Extended State Machine
• Adds variables to FSM model
• Variables can be read / written during transitions
• E.g., garage counter
5
January 25, 2018
Extended State Machine
• E.g., garage counter extended state machine
• Adds a variable: c
• Indicated in state machine
• NOT input or output
6
January 25, 2018
Extended State Machine
7
January 25, 2018
Aside: Mealy vs. Moore State Machines
Mealy
• Output determined by state + input
• Output occurs during transition
Moore
• Output determined by state only
• Output occurs within new state
8
January 25, 2018
Extended State Machines
General notation:
9
January 25, 2018
Extended State Machines
All variables must be declared (in addition to inputs, outputs)
10
January 25, 2018
Extended State Machines
Variables initialized in initial transition
11
January 25, 2018
Extended State Machines
Guard / action same as regular FSM, can also refer to variables
12
January 25, 2018
Extended State Machines
Transitions have an additional line to modify variable
13
January 25, 2018
Extended State Machines
Variable modified after guard evaluated and output produced
• Variable used in guard / output before it’s modified
• Similar to post increment (e.g., x = i++)
14
January 25, 2018
Extended State Machines
More than one ”set action” is allowed for each transition
• Actions made in sequence (e.g., i++ , j--)
15
January 25, 2018
Outline
• Motivation
• Extended state machine
• Example
16
January 25, 2018
Example
Stop light with pedestrian button
• Time triggered state machine (1 Hz)
• 60 seconds in red then transitions to green
• Remains green until pedestrian present
• Must stay green for at least 60 seconds
• Transitions from green to “pending” if 60 seconds not done
• Transitions to yellow for 5 seconds
• Then red for 60 seconds…
17
January 25, 2018
Example
States: red, green, pending, yellow
Variable: count: { 0, 1, …, 60 }
Inputs: pedestrian: pure
Outputs: sigR, sigG, sigY : pure
18
January 25, 2018
Example
Start w/ states
green
red pending
yellow
19
January 25, 2018
Example
Start w/ states
green
count = 0
red pending
yellow
20
January 25, 2018
Example
Go from red to green? Yes, when count >= 60
count >= 60 / sigG green
count := 0
count = 0
red pending
yellow
21
January 25, 2018
Example
Use default transition to update count in red state
count >= 60 / sigG green
count := 0
count = 0
red pending
count++
yellow
22
January 25, 2018
Example
Use default transition to update count in red state
count >= 60 / sigG green
count := 0
count = 0
red pending
count++
yellow
23
January 25, 2018
Example
Now you fill in the remaining transitions…
Stop light with pedestrian button
• Time triggered state machine (1 Hz)
• 60 seconds in red then transitions to green
• Remains green until pedestrian present
• Must stay green for at least 60 seconds
• Transitions from green to “pending” if 60 seconds not done
• Transitions to yellow for 5 seconds
• Then red for 60 seconds…
24
January 25, 2018
Example
25
January 25, 2018
