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
- five-tuple (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
- four-tuple (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 bi-partite 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 1-in-1-out
- marked graph: all places 1-in-1-out
- 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
- k-bounded nets
- no place ever contains > k tokens
- 1-bounded 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
- S-invariants
- T-invariants
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