8,797 views
33 votes
33 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^*$

2 Answers

Best answer
58 votes
58 votes
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
16 votes
16 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

40 votes
40 votes
10 answers
2
Kathleen asked Sep 17, 2014
6,936 views
Consider the set \(\{a, b, c\}\) with binary operators \(+\) and \(*\) defined as follows:$$\begin{array}{|c|c|c|c|} \hline \textbf{+} & \textbf{a}& \textbf{b} &\textbf{c...