in Set Theory & Algebra
5,147 views
23 votes

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^*$
in Set Theory & Algebra
5.1k views

Subscribe to GO Classes for GATE CSE 2022

2 Answers

47 votes
 
Best answer
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).
edited by
by

16 Comments

U are right
1
why not inverse?
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.
13
ok. similar to division by zero. not defined. illogical. doesnt make sense.

 

thanks.
2
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
7
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 ???
0
Can we say Commutative property also fails here?
0

@  Bhagirathi

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

0
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.
0
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?
0
nice logic @ mgrwt
0
@Mk Utkarsh-No your identity element is present in the set $\sum^*$ as

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

 sorry i forgot to mention i was talking about option D

0
this structure will be a monoid
0
Why option c is not correct ?,i know option A is correct but what about option C
0
Isnt that the first statement of answer?
0
10 votes

 

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

Answer:

Related questions

Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true