in Theory of Computation retagged by
496 views
1 vote
1 vote

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.

in Theory of Computation retagged by
496 views

2 Answers

0 votes
0 votes

Answer:

1 comment

@soujanyareddy13 , Could you please ellaborate a little more ?

0
0
0 votes
0 votes

@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.

Related questions