Consider the set Sigma* of all strings over the alphabet Sigma = {0, 1}, with the concatenation operator for strings. A. Sigma* does not form a group. B. Sigma* forms a non-commutative group. C. Sigma* does not have a right identity element. D. Sigma* forms a group if the empty string is removed from Sigma*.

GATE 2003 · Discrete Mathematics · Group Theory · medium

Answer: Sigma* under concatenation is a monoid but not a group (no inverses for non-empty strings), so the correct statement is A.

1. Check the easy axioms and the identity: concatenation of two strings is a string (closure), is associative ((u.v).w = u.(v.w)), and the empty string e satisfies e . w = w and w . e = w. So Sigma* does have an identity - this already refutes statement C (a right identity exists)
2. Show inverses fail, so it is not a group: for any non-empty string u, |u . x| = |u| + |x| >= 1 > 0 = |e|, so no x makes u . x = e; only the empty string is invertible. Therefore Sigma* is not a group (refuting B), and removing the empty string would delete the only identity, so D is also false. The correct statement is A: Sigma* does not form a group