Deterministic Finite Automaton - DFA As A Transition Monoid

DFA As A Transition Monoid

Alternatively a run can be seen as a sequence of compositions of transition function with itself. Given an input symbol, one may write the transition function as, using the simple trick of currying, that is, writing for all . This way, the transition function can be seen in simpler terms: it's just something that "acts" on a state in Q, yielding another state. One may then consider the result of function composition repeatedly applied to the various functions, and so on. Using this notion we define . Given a pair of letters, one may define a new function, by insisting that, where denotes function composition. Clearly, this process can be recursively continued. So, we have following recursive definition

where is empty string and

where and .

is defined for all words . 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, one can reconstruct a, and so the two descriptions are equivalent.