|
|
|
|
|
Transformation SemigroupA 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 group holds |Q| \leq |G|, so at most |G| - the group order - states suffice to represent any group G by permutations of Q. In fact the group itself can function as state-set. 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 http://piazza.iae.nl/users/benschop/preface.htm ).
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|