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

U are right

---

why not inverse?

---

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.

---

ok. similar to division by zero. not defined. illogical. doesnt make sense.

 

thanks.

---

think about concatinating  string with some any other string to get null string...you will not find any such string so there is no inverse thats it

---

difference between right identity and left identity element ?

There exists identity element e such that,

                1) a*e = a for all a belongs to set    (right identity)

                2) e*a = a for all a belongs to set     (left identity)

Is this correct ???

---

Can we say Commutative property also fails here?

---

@  Bhagirathi

your answer always crystal clear... :) it proves me very helpful..

---

of course Anil

$ab \neq ba$

$ab$ is string that start with a and end with b , and have length 2 while $ba$ is a string that starts with b and ends with a and have length 2 , clearly both are different strings.

---

Identity element for concatenation is empty string ϵ and that is not in group so can we say that there is no identity element in set so it is not even a monoid?

---

nice logic @ mgrwt

---

@Mk Utkarsh-No your identity element is present in the set $\sum^*$ as

$\sum^*=(0+1)^*$

---

Ayush Upadhyaya sorry i forgot to mention i was talking about option D

---

this structure will be a monoid

---

Why option c is not correct ?,i know option A is correct but what about option C

---

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 .