Editing Deterministic finite automaton (section)

==As a transition monoid==
A run of a given DFA can be seen as a sequence of compositions of a very general formulation of the transition function with itself. Here we construct that function.

For a given input symbol <math>a \in \Sigma</math>, one may construct a transition function <math>\delta_a : Q \rightarrow Q</math> by defining <math>\delta_a(q) = \delta(q,a)</math> for all <math>q \in Q</math>.  (This trick is called [[currying]].) From this perspective, <math>\delta_a</math> "acts" on a state in Q to yield another state.  One may then consider the result of [[function composition]] repeatedly applied to the various functions <math>\delta_a</math>, <math>\delta_b</math>, and so on.  Given a pair of letters <math>a, b \in \Sigma</math>, one may define a new function <math>\widehat\delta_{ab}=\delta_a \circ \delta_b</math>, where <math>\circ</math> denotes function composition.

Clearly, this process may be recursively continued, giving the following recursive definition of <math>\widehat\delta : Q \times \Sigma^{\star} \rightarrow Q</math>:
:<math>\widehat\delta ( q, \epsilon ) = q</math>, where <math>\epsilon</math> is the empty string and
:<math>\widehat\delta ( q, wa ) = \delta_a(\widehat\delta ( q, w ))</math>, where <math> w \in \Sigma ^*, a \in \Sigma </math> and <math>q \in Q</math>.
<math>\widehat\delta</math>  is defined for all words <math>w\in\Sigma^*</math>.  A run of the DFA is a sequence of compositions of <math>\widehat\delta</math> with itself.

Repeated function composition forms a [[monoid]]. For the transition functions, this monoid is known as the [[transition monoid]], or sometimes the ''transformation semigroup''. The construction can also be reversed: given a <math>\widehat\delta</math>, one can reconstruct a <math>\delta</math>, and so the two descriptions are equivalent.