Transformation semigroup Guide, Meaning , Facts, Information and Description
A closed system S(#) with an associative operation (#) is called a 'semigroup'\ , where:. . . for all a, b, c in S holds (a#b)#c = a#(b#c)
Normal string concatenation is associative, and it is the standard for notation, hence : (ab)c = a(bc) = abc (unique, independent of bracketing, also called a 'context-free' algebra) for all a, b, c in S.
A finite associative system is called semigroup because historically it arose as a generalization of group theory in the early 1900's, namely by deleting the one identity element and unique inverse condition in a group (so only associativity is left as defining condition).
The characteristic representation:
- of a finite group G is by permutations of an underlying set Q (of letters, or states), and :
- of a semigroup S is by transformations of a state-set Q.
For a semigroup S at most |Q| = |S|+1 states suffice for its representation by transformations of Q : either Q = S , or Q = { S, e } where e is a left identity of S (in case S does not have one): ea = a for all a in S.
Each element a of S transforms q in Q into next-state qa in Q. So each semigroup element is a mapping a : Q --> Q , thus a function that maps the state-set Q into itself.
For any finite semigroup, such representation by transformations of a (state-) set implies the name transformation semigroup , and its essential importance for the structure theory of Finite State Machines.
Notice that function composition ab is defined by q(ab) = (qa)b for all states q in Q. This is the essence of associative algebra resp. semigroups : it is the algebra of function composition, which is *not* commutative, since ab and ba may be different transformations of Q, just as f(g(x)) =/= g(f(x)) in general, here denoted in the more sensible righthand notation : x(gf) =/= x(fg).
Transformation Semigroups form the basic algebra for Finite State Machines (FSM) or Automata, in fact equivalent to function composition as the essential algebra for Digital Networks -- viewing a state machine as a network composition of coupled smaller state machines, of which there are five basic types (since there are 5 non-isomorphic semigroups of order 2, with clear engineering interpretations) see : Digital Network Theory
This is an Article on Transformation semigroup. Page Contains Information, Facts Details or Explanation Guide About Transformation semigroup