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, s₀, A). For every word w in Σ^*, let T_w be the function from S->S defined as follows for all s in S:

if w=λ, T_w(s) = s (the empty word does not change the state)

if w=σ in Σ, T_w(s)=T(s, σ)

if w=σv for σ in Σ and v in Σ^*, then T_w(s)=T_v(T(s, σ))

Let T(M) denote the set {T_w : w in Σ^*}. It can be shown that, for all v,w in Σ^*, T_w o T_v = T_vw. 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.