TOC Grand Test 1 Question 27 - Gatebook

Question

Consider languages L₁ and L₂ over {0,1} alphabet .

                                L2= { w | w contains some x as a substring and x belongs to L1 }

Which of the following must be true?
I. If L₁ is regular, L₂ is also regular.
II. If L₁ is CFL, L₂ is also CFL.
III. If L₁ is recursive, L₂ is also recursive

• A. I and II only
• B. I, II and III
• C. I and III only
• D. II and III only

Answer 1

Take $L1 = \Sigma *$ and let $x = aaabbb$ which belongs to L1 

And let $L2 =\left \{ a^{n}b^{m} | n < m\right \}$ 

Hence, $aaabbbb$ belongs to L2 but $x$ is a substring of $aaabbbb$ which makes first statement false .

---

Let $L1 = a^n b* a* b^n$ and let $x = ab$ which belongs to L1

And Let $L2 = \left \{ a^n b^n c^m | n>m, n,m >=0 \right \}$ 

Hence, $ab$ belongs to L2 but $x$ is a substring of $ab$ which makes second statement also false .

---

Then how the answer is B).

Comments

Okk !! That now makes sense why "only" was used there . For a set, it should include all strings, not some, otherwise it will violate set property.

---

Again a very big nitpick :)

---

@Kapil can you point out the question sir is talking about ? Plus is the answer B?. And you have taken a specific instance of x and in question x can be anything. Better if we assume x to be NULL. and l2 to be something.