Semigroup presentation ($⟨X\mid u_i=v_i⟩$)

A semigroup presentation specifies generators $X$ and equalities between nonempty words. The resulting semigroup is the quotient of the free semigroup $X^{+}$ by the smallest congruence containing these equalities. Two words are equal precisely when one can be transformed into the other by finitely many replacements in contexts, using the defining equalities in either direction.

A semigroup presentation is finite when both its generator set and its list of defining equalities are finite. A finite transition table for a Turing machine can be encoded this way: state-and-tape words simulate transitions, boundary rules supply blank cells, and halting-state rules erase the configuration to one distinguished symbol.