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:
“A transition from an author’s books to his conversation, is too often like an entrance into a large city, after a distant prospect. Remotely, we see nothing but spires of temples, and turrets of palaces, and imagine it the residence of splendor, grandeur, and magnificence; but, when we have passed the gates, we find it perplexed with narrow passages, disgraced with despicable cottages, embarrassed with obstructions, and clouded with smoke.”
—Samuel Johnson (1709–1784)