State Machines and Petri Nets
OVERVIEW
MODELING PROCESS AND STRUCTURE
 often need some abstract expression of the flow
of control through a system
 system may be sequential
 system may be concurrent, asynchronous
 finite state machine (FSM)
 used to specify control flow, sequential system
 also called finite state automaton (FSA),
deterministic finite automaton (DFA)

Petri net (Pnet)
 used to specify control flow in asynchronous
concurrent systems
BASIC FINITE STATE MACHINES
 fivetuple (Q,I,d,S,F)
 Q: finite set of states
 I: the alphabet, finite set of input symbols
 d: Q x I > Q, transition function (partial)
 S: element of Q, start state
 F: subset of Q, final states (may be empty)
 transition function represented as
 labeled directed graph
 table, or matrix
 FSM examples on board
FORMAL LANGUAGES
 formally, a language is a
 set
 set of strings
 strings of symbols from some alphabet
 let alphabet be S (set of symbols)
 S* is set of all possible strings from symbols in S
 L a subset of S* is a language
 FSM can recognize/generate regular languages
 note FSM with output
 examples on board
CHOMSKY HIERARCHY
 Classification of Languages, Automata
ranked by increasing complexity and power
 FSM
 regular languages, regular expressions
 Push Down Automata (PDA)
 context free languages, context free grammars
 Linear Bounded Automata (LBA)
 context sensitive languages
 Turing Machine (TM)
 Venn diagram on board
BASIC PETRI NETS
 fourtuple (P,T,F,m)
 P: finite set of places
 T: finite set of transitions
 F: subset of (P x T) U (T x P), the flow relation
 m: P > { 0, 1, 2, ... }, the initial marking
 represented by bipartite directed graph
 terms
 marked (place), marking (net)
 enabled (transition)
 fire (transition)
 firing rule, firing sequence
NET STRUCTURE
 net structure represents
 sequential actions
 selection (choice, conflict) (nondeterminism)
 concurrent threads of control
 synchronization
 special structure
 FSM: all trans 1in1out
 marked graph: all places 1in1out
 confusion: mixing conflict and concurrency
 mutual exclusion
NET INTERPRETATION in modeling systems
 transitions: system events
 e.g., allocate a resource
 places: system conditions (pre, post)
 e.g., resource is available
 token: condition holds
 enabled transition:
 all preconditions for an event hold
 fire a transition:
 event occurs, preconditions gone, postconditions hold
NET PROPERTIES
 kbounded nets
 no place ever contains > k tokens
 1bounded is safe
 conservative
 no tokens created or destroyed
 liveness
 all transitions can eventually be fired
 no deadlock
 net languages
 assign symbol from alphabet to each transition
 acceptance by either
 no transitions enabled
 final states
NET ANALYSIS
 boundedness
 reachability tree
 coverability and omega
 Sinvariants
 Tinvariants
NET EXTENSIONS
 added notational flexibility, expressiveness
 some add computational power
 popular extensions
 inhibitor arcs
 priorities on transitions
 timing
 colored tokens
 firing rule alterations
 parallel finite automata (PFA)
 debit arcs and anihilation
 C/E systems