# semigroup

**semigroup** A very simple algebraic structure comprising a set *S* on which there is defined an associative operation denoted by ◦ (compare group). The operator ◦ is assumed to take operands from the set and produce results that are also in *S*. When the set *S* is finite a semigroup can be described by giving the Cayley table of the operation ◦; otherwise it can be described by giving a rule for ◦.

Examples of semigroups include: strings with the operation of concatenation (joining together); the set of *n*×*n* matrices together with the operation of multiplication; the set of transformations of a set and the operation of composing functions; the integers and the operation of choosing the maximum (or minimum) of two elements. The set of integers together with subtraction does not constitute a semigroup.

Semigroups play a major role in the theory of sequential machines and formal languages. If M is a sequential machine then any input string induces a function over the state-set of M. The set of all such induced functions forms a *semigroup of the machine* under function composition (see Myhill equivalence, Nerode equivalence). Semigroups are also used in certain aspects of computer arithmetic. See also free semigroup, transformation semigroup, monoid.

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**semigroup**