Directed graph State diagram

a directed graph

a classic form of state diagram finite state machine or finite automaton (fa) directed graph following elements (q,Σ,z,δ,q0,f):

vertices q: finite set of states, represented circles , labeled unique designator symbols or words written inside them
input symbols Σ: finite collection of input symbols or designators
output symbols z: finite collection of output symbols or designators

the output function ω represents mapping of ordered pairs of input symbols , states onto output symbols, denoted mathematically ω : Σ × q→ z.

edges δ: represent transitions 1 state caused input (identified symbols drawn on edges). edge drawn arrow directed present state next state. mapping describes state transition occur on input of particular symbol. written mathematically δ : q × Σ → q, δ (the transition function) in definition of fa given both pair of vertices connected edge , symbol on edge in diagram representing fa. item δ(q,a)= p in definition of fa means state named q under input symbol a, transition state p occurs in machine. in diagram representing fa, represented edge labeled pointing vertex labeled q vertex labeled p.
start state q0: (not shown in examples below). start state q0 ∈ q represented arrow no origin pointing state. in older texts, start state not shown , must inferred text.
accepting state(s) f: if used, example accepting automata, f ∈ q accepting state. drawn double circle. accept state(s) function final (halt, trapped) states.

for deterministic finite automaton (dfa), nondeterministic finite automaton (nfa), generalized nondeterministic finite automaton (gnfa), or moore machine, input denoted on each edge. mealy machine, input , output signified on each edge, separated slash / : 1/0 denotes state change upon encountering symbol 1 causing symbol 0 output. moore machine state s output written inside state s circle, separated state s designator slash / . there variants combine these 2 notations.

for example, if state has number of outputs (e.g. a= motor counter-clockwise=1, b= caution light inactive=0 ) diagram should reflect this : e.g. q5/1,0 designates state q5 outputs a=1, b=0. designator written inside state s circle.

example: dfa, nfa, gnfa, or moore machine

s1 , s2 states , s1 accepting state or final state. each edge labeled input. example shows acceptor strings on {0,1} contain number of zeros.

example: mealy machine

s0, s1, , s2 states. each edge labeled j / k j input , k output.

^ taylor booth (1967) sequential machines , automata theory, john wiley , sons, new york.
^ john hopcroft , jeffrey ullman (1979) introduction automata theory, languages, , computation, addison-wesley publishing company, reading mass, isbn 0-201-02988-x
^ edward j. mcclusky, introduction theory of switching circuits, mcgraw-hill, 1965