7

This is related to a course I'm taking in computer science theory.

Let $\sum$ be an alphabet. Then the set of all strings over $\sum$, denoted as $\sum^*$ has the operation of concatenation (adjoining two strings end to end). Clearly, concatenation is associative, $\sum^*$ is closed under concatenation, and the identity element is the empty string. I'm also taking a course in modern algebra, so I naturally ask can $\sum^*$ be formed into a group? Three of the four group axioms are satisfied.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236

2 Answers2

6

It is not a group, it is a monoid, which is essentially a group without inverses. The natural thing to do if you want a group is to just arbitrarily allow inverses. So you would consider strings whose letters are of the form $a$ or $a^{-1}$ where $a \in \Sigma$. You say that two strings are equivalent if you can get from one to another by adding or deleting pairs of the form $aa^{-1}$ or $a^{-1}a$. Then the set of equivalence classes of strings is a group under concatenation.

This construction is called the free group on $\Sigma$.

Jim
  • 30,682
2

No, $\Sigma^*$ is not a group (unless $\Sigma = \emptyset $, in which case $\Sigma ^*$ is a trivial group with one element). The reason is that the only element having an inverse is the empty word. So if $a\in \Sigma$, then $a$ as an element of $\Sigma ^*$ does not have an inverse (rigorously, note that the length of words never decreases upon concatenation).

What $\Sigma ^*$ is is an example of a monoid. A monoid is an algebraic structure satisfying all axioms of a group except the requirement of identities. In fact, $\Sigma ^*$ is the free monoid on the set $\Sigma$. There is also the obvious notion of a commutative monoid, and a certain quotient of $\Sigma^*$, obtained by allowing elements to commute, gives rise to the free commutative monoid $\Sigma ^+$.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236