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

Question

Which of the following is correct?

• A. $(01)^* \cap (10)^* = \phi$
• B. $(a + b + c)^* = a^*b^*c^* + a^*b^* + c^* + c^*a^*b^*$
• C. $(p + q)^* p + (p + q)^* q + \epsilon = (p^* q^*)^*$
• D. $( y + z)^*  \cap (y + z)^* yz   \neq ( y + z)^* yz$

Comments

Why A is wrong?

---

@ Vasu 

(01)* have at least one 1 .

(10)* also have at least one 1.

so  (01)* ∩ (10)* =  ∅ must be false because  (01)* ∩ (10)*  have at least one 1 in common..

---

In ( p + q)* p + (p + q)* q + ε = (p* q*)*

->  How ( p + q)* (p + q) + ε  is equal to (p* q*)*  as we know this identity (a+b)*=(a*b*)*??

Please explain it

---

@amitpawar Look at the answer here.

https://gateoverflow.in/143465/theory-of-computation-test-2-14

---

(01)* = ( EMPTY, 01, 0101, 010101, ...)

(10)* = ( EMPTY, 10, 1010, 101010, ...)

 

I don't find any common element there.

---

Any one can explain  Please about option B & D?

---

see that epsilon is common in both......

---

For option B) just produce a contradictory string like... bac,acb...fails here

                 D) We know that, (a+b)* = is the universal set , it contain all possible string

                     ( y + z)*  ∩ (y + z)* yz    ≠   ( y + z)* yz

                (All Strings) ∩ (Strings ending with yz) =  Strings ending with yz

---

( p + q)* (p + q) + ε = ( p + q )*  As Per as (R)*R + ε = (R)*, And  ( p + q )* = (p* q*)* As per as  (a+b)*=(a*b*)*

---

IN option C

String pqqp can be generated from LHS but not from RHS

then how will it be correct?

---

ALL the 4 options are not correct is what i feel

---

@Aish you can read the answer here.

https://gateoverflow.in/143465/theory-of-computation-test-2-14

---

please agin check ,it is generating your string from both side  i.e pqqp

from LHS     ( p + q)* p + (p + q)* q + ε      =          (p+q) (p+q) (p+q) (p+q) = pqqp

from RHS      (p* q*)*                                   =         (p) (q) (q) (p)   =  pqqp

---

@varun

what i considered was if suppose it is (p¹ q²)²

it should give = > pqq for the first time then pqq for next time

so pqqpqq and so will not give pqqp

what i considered was for each time of outer loop both

p and q must be executed the same amount of time

guess i was wrong ther..right ?

Answer 1

A. False, $\epsilon$ is common in both $(01)^*$ and $(10)^*$

B. False, LHS contain strings as $abab, ababab$ etc RHS doesn't.

C.True, $(p+q)^*p+(p+q)^*q+\epsilon =$ strings over $\{p,q\}$ those ends with $p$     $+$ those ends with $q$    $ +$ those doesnt end with p or q (i.e, $\epsilon$) = all strings over $\{p,q\}$ , i.e,$ (p+q)^* = (p^*q^*)^*$

D.False , all strings over $\{y,z\}$ (that also includes all strings ending with $yz$ ) $\bigcap$ all strings $\{y,z\}$ ending with $yz= (y+z)^*yz$