Question

Consider the set $\sum ^{\ast }$ of all strings over the alphabet $\sum =\{0,1\}.\sum ^{\ast }$ 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. Forma a group if the empty string is removed from $\sum ^{\ast }$

Answer 1

The correct option is A Does not form a group

$\sum =\{0,1\}$
$\sum ^{\ast }=\{0,1{\}}^{\ast }$
$=\{ϵ,0,1,01,10,11,000\dots \dots \}$
So $(\sum ^{\ast },.)$ is a group if and only if the following conditions are satisfied.
1. . (Concatenation) is a closed operation.
2. . is an associative operation
3. There is an identity
4. Every element of $\sum ^{\ast }$ has a inverse

Condition 1: $\ast$ is a closed operation because for any ${\omega }_1ϵ\sum ^{\ast }$ and
${\omega }_2ϵ\sum ^{\ast },{\omega }_1.{\omega }_2ϵ\sum ^{\ast }$

Condition 2: For any string $x,y,zϵ\sum ^{\ast }$
$x.(y.z)=(x.y).z$
So it is associative for example let
$x=01,y=11,z=00$ then
L.H.S. $=x.(y.z)$
$=01.\left(11.00\right)=01.\left(1100\right)$
$=011100$
R.H.S. $=(x.y).z$
$=\left(01.11\right).00=\left(0111\right).00$
$=011100$

Condition 3: The Identity is $ϵ$ or empty string because for any string $\omega ϵ\sum ^{\ast }$
$ϵ\omega =\omega ϵ=\omega$
Now, since $\epsilon ϵ\sum ^{\ast }$, identity exists.

Condition 4: There is no inverse exist for $\sum ^{\ast }$ because any string $\omega ϵ\sum ^{\ast }$, there is no string ${\omega }^{-1}$ such that $\omega .{\omega }^{-1}=\epsilon ={\omega }^{-1}\omega$
So $\sum ^{\ast }$ with the concatenation operator for strings doesn't form a group but it does form a monoid.