Transition monoid
From Wikipedia, the free encyclopedia
The transition monoid is a monoid constructed from the transition function of a deterministic finite automaton (DFA). The elements of the transition monoid are functions mapping states (of the DFA) to states. The DFA's transition monoid abstracts the observable effect of input words on the DFA's state; it contains no information about recognition or rejection of words by the DFA.
[edit] Formal definition
Let M be a DFA (S, Σ, T, s0, A). For every word w in Σ*, let Tw be the function from S->S defined as follows for all s in S:
- if w=λ, Tw(s) = s (the empty word does not change the state)
- if w=σ in Σ, Tw(s)=T(s, σ)
- if w=σv for σ in Σ and v in Σ*, then Tw(s)=Tv(T(s, σ))
Let T(M) denote the set {Tw : w in Σ*}. It can be shown that, for all v,w in Σ*, Tw o Tv = Tvw. That is, the set T(M) is closed under function composition; and it contains Tλ, which is the identity function on S. Since function composition is by definition associative, (T(M), o, Tλ) is a monoid: the transition monoid of the DFA M.
[edit] Applications
The syntactic monoid of a formal language is isomorphic to the transition monoid of the minimal automaton accepting the language.
[edit] Bibliography
- The Algebraic Theory of Semigroups, A. H. Clifford and G. B. Preston. American Mathematical Society, 1961 (volume 1), 1967 (volume 2).
- Algebraic Theory of Automata, F. Gecseg and I. Peak. Akademiai Kiado, Budapest, 1972.
