Editing State diagram (section)

== Directed graph ==
[[Image:Directed.svg|125px|thumb|A [[directed graph]]]]

A classic form of state diagram for a [[Deterministic finite automaton|finite automaton]] (FA) is a [[directed graph]] with the following elements (Q, Σ, Z, δ, q<sub>0</sub>, F):<ref name=Boo67>[[Taylor Booth (mathematician)|Taylor Booth]] (1967) ''Sequential Machines and Automata Theory'', John Wiley and Sons, New York.</ref><ref name=HoU79>[[John Hopcroft]] and [[Jeffrey Ullman]] (1979) ''[[Introduction to Automata Theory, Languages, and Computation]]'', Addison-Wesley Publishing Company, Reading Mass, {{ISBN|0-201-02988-X}}</ref>

*'''Vertices Q''': a finite set of states, normally represented by circles and labeled with unique designator symbols or words written inside them
*'''Input symbols Σ''': a finite collection of input symbols or designators
*'''Output symbols Z''': a finite collection of output symbols or designators

The output function ω represents the mapping of ordered pairs of input symbols and states onto output symbols, denoted mathematically as '''ω''' : '''Σ''' × '''Q'''→ '''Z'''.

*'''Edges δ''': represent transitions from one state to another as caused by the input (identified by their symbols drawn on the edges). An edge is usually drawn as an arrow directed from the present state to the next state. This mapping describes the state transition caused by an input. This is written mathematically as '''δ''' : '''Q''' × '''Σ''' →   '''Q''', so δ (the transition function) in the definition of the FA is given by both the pair of vertices connected by an edge and the symbol on an edge in a diagram representing this FA. Item '''δ(q, a) = p''' in the definition of the FA means that from the state named '''q''' under input symbol '''a''', the transition to the state '''p''' occurs in this machine. In the diagram representing this FA, this is represented by an edge labeled by '''a''' pointing from the vertex labeled by '''q''' to the vertex labeled by '''p'''.
*'''Start state q<sub>0</sub>''': (not shown in the examples below). The start state q<sub>0</sub> ∈ Q is usually represented by an arrow with no origin pointing to the state. In older texts,<ref name=Boo67/><ref name="McC65">[[Edward J. McClusky]], Introduction to the Theory of Switching Circuits, McGraw-Hill, 1965</ref> the start state is not shown and must be inferred from the text.
*'''Accepting state(s) F''': If used, for example for accepting automata, F ∈ Q is the [[accept state|accepting state]]. It is usually drawn as a double circle. Sometimes the accept state(s) function as "'''F'''inal" (halt, trapped) states.<ref name=HoU79/>

For a [[deterministic finite automaton]] (DFA), [[nondeterministic finite automaton]] (NFA), [[generalized nondeterministic finite automaton]] (GNFA), or [[Moore machine]], the input is denoted on each edge. For a [[Mealy machine]], input and output are signified on each edge, separated with a slash "/": "1/0" denotes the state change upon encountering the symbol "1" causing the symbol "0" to be output. For a [[Moore machine]] the state's output is usually written inside the state's circle, also separated from the state's designator with a slash "/". There are also variants that combine these two notations.

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

=== Example: DFA, NFA, GNFA, or [[Moore machine]] ===
''S''<sub>1</sub> and ''S''<sub>2</sub> are states and ''S''<sub>1</sub> is an '''accepting state''' or a '''final state'''. Each edge is labeled with the input. This example shows an acceptor for binary numbers that contain an even number of zeros.
:[[Image:DFAexample.svg|200px|DFAexample.svg]]

=== Example: [[Mealy machine]] ===
''S''<sub>0</sub>, ''S''<sub>1</sub>, and ''S''<sub>2</sub> are states. Each edge is labeled with "''j'' / ''k''" where ''j'' is the input and ''k'' is the output.
:[[Image:Mealymachine jaredwf.png|State diagram of a simple Mealy machine]]