5,147 views

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

1. does not form a group
2. forms a non-commutative group
3. does not have a right identity element
4. forms a group if the empty string is removed from $\Sigma^*$

Subscribe to GO Classes for GATE CSE 2022

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).
by

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?

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)^*$

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?

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