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.
Read more about this topic: Deterministic Finite Automaton
Famous quotes containing the word transition:
“The most remarkable aspect of the transition we are living through is not so much the passage from want to affluence as the passage from labor to leisure.... Leisure contains the future, it is the new horizon.... The prospect then is one of unremitting labor to bequeath to future generations a chance of founding a society of leisure that will overcome the demands and compulsions of productive labor so that time may be devoted to creative activities or simply to pleasure and happiness.”
—Henri Lefebvre (b. 1901)