# State Machines and Petri Nets

## 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)
• any computable sets
• 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)
• 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
• 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