SWE 300
Software Process and Modeling
State Machines
This is the instructor’s notes. Students has to read the required textbook to understand the covered concepts.
State Machines
• The next few lectures will show you
how to model systems using State
Machines
> State Machine Basics
» motivation, basic concepts, notation, simple examples
> State Machine Variations
» modeling complex systems, variables, actions, non-
determinism
> Statecharts
» a specific, popular graphical approach
Why State Machines?
• Goal: provide simple abstractions of
complex systems
• All computer systems are state
machines
> registers and memory are state
> changes are transitions between states
> a program defines the way in which initial
states are transformed into final states
> a programming language determines a set
of programs (and hence, a set of machines)
• Primary challenge will be to represent
these very complex machines with
simpler (more abstract) machines that
we can reason about
• Essence of modeling is choosing those
characteristics to model and those to
abstract away from
State Machines Are Used
• When it is possible to abstract away
irrelevant details, leaving only a small
number of states
• When we want to examine every
possibility using model checking
• For communication protocols and
complex distributed algorithms (e.g.,
cache coherency)
Some Notes
• State machines are the modeling
foundation for all of the other forms of
modeling that we will be looking at
(including Z, CSP, Temporal Logic, etc.)
• No standard notation, although the
concepts are widely agreed upon
• Level of rigor will vary depending on
needs and mood
Informally ...
• A state machine captures the idea that
a system progresses through a set of
states by performing (or responding to)
a set of actions
• Thus there are two key concepts
> States
> Actions
Characteristics
• A state machine definition must say
> what the possible states are
> what initial states the machine may start in
> what the possible actions are
> how the state changes when actions occur
What is a State?
• A snapshot of the system
> values of memory, registers
• Set of values for variables
> snapshot of running program’s data
• Control location(s)
> snapshot of where a program is in its
execution sequence(s)
• Contents of communication channels
> snapshot of a communication state
A (Very) Simple State Machine
• World’s simplest (and most boring)
state machine
stop
• States: {stop}
• Actions: {}
• Initial state: {stop}
Another Simple Example
alarm
beep
• States: {alarm}
• Actions: {beep}
• Initial state: {alarm}
A More Interesting Example
key gas brake
M1 off idle moving crashed
• States: {off, idle, moving, crashed}
• Actions: {key, gas, brake}
• Initial state: {off}
A Small Variation
key gas brake
M2 off idle moving crashed
key
• One action may cause alternative
transitions from the same state
• This is referred to as non-determinism
• Also note: machine now has a possibly
infinite number of steps that it can take
Formal Definition
• A state machine M is a 4-tuple (S, I, A, T)
with
S : set of possible states
I : set of initial states (subset of S)
A : set of actions
T : transition “relation” over S x A x S
• When S is finite, M is a finite state
machine
Notes
For a State Machine (S, I, A, T)
T is often represented by the symbol
(Greek Delta).
T is sometimes written in the form
S x A S, making it a true relation
Transitions
• (s1, a, s2) is in T when there is an arrow
from s1 to s2 labeled a
• T is a relation because of
nondeterminism (two arrows from the
same source and with the same label, to
different targets)
• When T is a function we say M is a
deterministic state machine
• Actions are sometimes called labels,
actions, or state transitions
• A is sometimes called the alphabet of M
Car Example (M1)
• S = { off, idle, moving, crashed }
• I = { off }
• A = { key, gas, brake }
• T = { (off, key, idle), (idle, gas, moving),
(moving, brake, crashed) }
Car == (
{ off, idle, moving, crashed },
{ off },
{ key, gas, brake },
{ (off, key, idle), (idle, gas, moving), (moving,
brake, crashed) }
)
Executions
• Each triple, (s,a,s’) in T is called a step
of M
• An execution is a finite or infinite
sequence
<s0, a1, s1, a2, s2, ... , >, where s0 is an initial state
of M, and for all i, (si, ai+1, si+1 ) is in T
(note must end in a state if finite and non-
empty)
• A state is reachable if it is the final state
of some execution
Executions - Examples
• Examples
<off, key, idle, gas, moving, brake, crashed>
<off, key, idle>
<off, key, off, key, off, key, ...>
• For a finite execution, the last state is
called a final state of M (note: may be
different elsewhere)
Traces
• A (event-based) trace is the sequence of
actions of an execution
> < key, gas, brake >
> <key>
> <key, key, key, ... >
• A (state-based) trace is the sequence of
states of an execution, or the sequence
<s> for any initial state, s, in I.
> < off, idle, moving, crashed>
> <off>
> <off, off, off, ... >
Behavior
• The behavior of a machine M (Beh(M))
is the set of all traces of M
Event based:
> {<>, <key>, <key, gas>, <key, gas, brake>}
> {<>, <key>, <key, key>, <key, gas>,
<key, key, gas>, ...>
• Behaviors are prefix-closed
• Note: a finite state machine can have
infinite behavior
• Question: can an infinite state machine
have finite behavior?
Infinite State Machines
• In general, state machines may not
have a finite numbers of states
• Example: integer counter
inc inc inc
0 1 2 3
• How can we write this state machine
down?
Informally
We want something like this:
SimpleCounter == (
{0, 1, 2, ...},
{0},
{inc},
{(0,inc,1), (1,inc,2), (2,inc,3), ...}
)
But "..." is not very precise
Solution: you already know how
Using Sets and Logic
to Describe State Machines
• The set of states is easy:
• The transition for inc can be described
by:
Tinc == { (s,a,s’): A x {inc} x A s’ = s +1
}
where Tinc is the part of T that deals with inc
• In general, we have
T= Ta
a A
SimpleCounter == (A, {0}, {inc},
{ (s,a,s’): A x {inc} x s’ = s +1 })
Interfaces and Environments
• What is the difference between these
machines?
tick push-A
left right blue red
tock push-B
• In general, a machine operates in an
environment that can either observe an
event or cause an event to occur.
• Sometimes it helps to distinguish
between observed and initiated events,
or input and output actions
Abstraction
• In all of the examples we are obviously
representing only some of the behavior
of a system. This is called abstraction.
• Deciding what to abstract is determined
by
> taste
> what will fit on a page
> what you want to communicate to others
> what you want to reason about
> what can be checked by tools
> experience and practice
Unexpected Actions
• Consider the following machine
push-A
blue red
push-B
• What happens if I push button B when
the machine is in the blue state?
> Nothing
> It is undefined -- anything can happen
> It is an error
> It can’t happen We’ll adopt this interpretation
