Test by Bikram | Theory of Computation | Test 2 | Question: 14

Question

Which of the following is correct?

• A. $(01 )^* \cap (10)^*  =  \not{0}$
• B. $(x + y + z)^* = x^*y^*z^* + x^*y^* + z^* + z^*x^*y^*$
• C. $(p + q )^* p + ( p+q)^* q + \epsilon  =  (p^* q^*)^*$
• D. $(m + n)^* \cap  (m + n)^* mn \neq (m + n)^* mn$

Answer 1

A is false. Because Epsilon is present in both, So their intersection can't be Null.

B is false.

LHS = (x + y + z)* = All the string over the alphabet x, y, z.

RHS, It is easy to see that it doesn't contain all the string over x, y, z.

 C is True.

RHS = (p* q*)* = (p + q)* = All the string over the alphabet p, q.

LHS = (p + q)*p + (p + q)*q + $\epsilon$

$\Rightarrow$ LHS = (p + q)*(p + q) + $\epsilon$

The first part (p + q)*(p + q) contains all the string that is ending either with p or q. The second part contains $\epsilon$

Hence. It contains all the string over the alphabet p, q.

D is false.

$\sum$ * $\cap$ L = L.

So, (m + n)* $\cap$ (m + n)*mn = (m + n)*mn.

Comments

@hemant

But in option C

string pqqp is accepted by LHS and not by RHS 

---

@Aish, right side contains all the string of p and q. Carefully observe the * in (p*q*)*.

You can form pqqp as (p*q*)^2 = (p*q*) (p*q*) = (pqqp)

---

@hemant thanku :)