GATE CSE 2003 | Question: 7

Question

Consider the set $\Sigma^*$ of all strings over the alphabet $\Sigma = \{0, 1\}$. $\Sigma^*$ with the concatenation operator for strings

• A. does not form a group
• B. forms a non-commutative group
• C. does not have a right identity element
• D. forms a group if the empty string is removed from $\Sigma^*$

Answer 1

Identity element for concatenation is empty string $\epsilon$. Now, we cannot concatenate any string with a given string to get empty string $\implies$ there is no inverse for string concatenation. Only other 3 group properties -- closure, associative and existence of identity -- are satisfied.

Hence, ans should be (a).

Comments

Isnt that the first statement of answer?

---

identity element is there as $\epsilon.$

---

actually concatenation operator is a monoid and monoid only have identity but not inverse so it doesn't form a group

Answer 2

 

Closure? Yes.

Concatenate any string in $Σ^∗$ with a string $Σ^∗$, you get a string in $Σ^∗$.

---

Associativity? Yes.

Example: $a.(b.c)=(a.b).c=abc$

No counter example can be found.

---

Identity? Yes. The null string $\epsilon$

$x.\epsilon=x$

---

Inverse?

10110 concatenated with what gives null string? There can't be an inverse here.

If you think 10110.$\phi$ would work, then no.

$x.\phi=\phi$

• $\epsilon$ = null string.
• $\phi$ = null set.
• $\phi\neq\epsilon$

Here, inverse doesn't exist for any element except identity element.

So, this is a monoid.

 

Option A

Comments

1) closure exists take any string from Σ* do concatenation with anyother strong you will remain in same set of Σ*
2)associativity exists as strong concatenation is associative
3)indentity exist : a * e = e * a = a
                            here e can be epsilon
                            (any string ) . epsilon = epsilon . (any string )= (same string)
4) inverse : definition of inverse says it should exist for all element belonging to the given set but it only exists for ε. 

therefore it does not form a group 
option a) says it does not form a group. ✓
option b) it says forms non commutative group a commutative group is abelian group it says non commutative group means a group which is non abelian yes it does not satisfy commutativity but it is not even a group ❌
option c) does not have a right identity element ❌
              infact both right and left identity exists
option d) forms a group if the empty string is removed from Σ* ❌
infact we won't even satisfy identity here as epsilon is removed no therefore inverse still won't exists.
if we only have epsilon as an element then it forms a group .

             

Answer 3

1) closure exists take any string from Σ* do concatenation with anyother strong you will remain in same set of Σ*
2)associativity exists as strong concatenation is associative
3)indentity exist : a * e = e * a = a
                            here e can be epsilon
                            (any string ) . epsilon = epsilon . (any string )= (same string)
4) inverse : definition of inverse says it should exist for all element belonging to the given set but it only exists for ε.

therefore it does not form a group
option a) says it does not form a group. ✓
option b) it says forms non commutative group a commutative group is abelian group it says non commutative group means a group which is non abelian yes it does not satisfy commutativity but it is not even a group ❌
option c) does not have a right identity element ❌
              infact both right and left identity exists
option d) forms a group if the empty string is removed from Σ* ❌
infact we won't even satisfy identity here as epsilon is removed no therefore inverse still won't exists.
if we only have epsilon as an element then it forms a group .