CMI2016-B-4

Question

Let $\Sigma  = \{0, 1\}$. Let $A, \: B$ be arbitrary subsets of $\Sigma^\ast$. We define the following operations on such sets:

• $ A+B :=  \{ w \in \Sigma^\ast \mid w \in A \text{ or } w \in B \}$
• $A \cdot B  :=  \{ uv \in \Sigma^\ast \mid u \in A \text{ and } v \in B \} $
• $ 2A  :=  \{ ww \in \Sigma^\ast \mid w \in A \}$

Is it true that $(A+B) \cdot (A+B) = A \cdot A + B \cdot B +2(A \cdot B)$ for all choices of $A$ and $B$? If yes, give a proof. If not, provide suitable $A$ and $B$ for which this equation fails.

Answer 1

Comments

@soujanyareddy13 , Could you please ellaborate a little more ?

Answer 2

@soujanyareddy13 , Saw your answer. Coud you please ellaborate on that a little more ?

Can’t we treat this problem like digital logic ?

(A+B)(A+B) = ( A or B ) and ( A or B ) = A or B = A + B. – LHS.

For RHS : X.X = X and X.Y = 0 ( if X != Y ) --(1) ---- for this case LHS = RHS – the eqn will be true.

                                           = XY ( if X = Y ) --(2). --- for this case eqn is false – suitable counter example.

Thus in general the eqn does not hold.

Answer 3

The Claim is:
For languages \(A,B\subseteq\Sigma^\ast\) the equality
\[(A\cup B)(A\cup B)=AA\;\cup\;BB\;\cup\;2(AB)\]

LHS = \((A\cup B)(A\cup B)\)
= \((A\cup B)\cdot(A\cup B)=AA\ \cup\ AB\ \cup\ BA\ \cup\ BB.\)
= $\{uv \in \Sigma^\ast | u \in A \text{ or } u \in B \text{ and } v\in A \text{ or } v\in B \}$

RHS = \(AA\cup BB\cup 2(AB)\)
= \(AA\cup BB\cup\{xx\mid x\in AB\}\)
= $\{w \in \Sigma^\ast | (w = uv | u \in A \text{ and } v \in A \text{ or } u\in B \text{ and } v\in B) \text{ or } (w = uvuv | u\in A \text{ and } v\in B)\}$

The definitions of both are different, therefore we can say that the claimed equality does not hold.

The Counterexample (already given)

Let \(A=\{0\}\) and \(B=\{1\}\).

Then from definition,$A + B=\{0,1\}$
so, \((A+ B).(A+ B)=\{00,01,10,11\}.\)

On the other hand,
$AA=\{00\}, BB=\{11\}, AB=\{01\},$

and by the definition of \(2(A)\),
$2(AB)=\{xx\mid x\in AB\}=\{0101\}$
Hence, $AA + BB + 2(AB)=\{00,11,0101\}\neq\{00,01,10,11\}$

This is most probably not the complete proof, but I tried as much as possible to show it formally.