MADE EASY TEST SERIES

Question

Consider languages L₁ and L₂ over alphabet Σ = {a, b}.
  L₁ is known to be a context-free language.

 L₂ = {w|w is prefix of w' ∈ L₁}

Which of the following is true ?

A> L₂ need not be CFL

B> L₂ will be regular

​​​​​​​C> L₂ will be CFL

D> None of the above

Answer 1

as far as i know Prefix of CFl will be in CFl ( see referrence) and now let's check whether it is regular or not

lets take L=aⁿbⁿc^md^m is a CFL..

now one of the prefix(L)= aⁿbⁿc^m ..

Now it is in CFl but not in regular, as we need to compare a's and b's...so i think it is just an example that prefix of CFL will not always be regular

so i think C should be the answer

Correct me if i am wrong

Refer::http://math.stackexchange.com/questions/270197/prove-by-grammar-or-closures-that-the-prefix-language-is-context-free

Comments

how L is not in CFL  aⁿbⁿc^md^m   ???

---

sorry, i misinterprated m with n

---

So, what should be the answer?

Answer 2

cfl is closed under INIT operation.

so, L2 is cfl but partial regular also

Comments

Are you sure, Cfl is closed under init? Could you please prove the same by giving some logic.

---

yeah

prefix is closed under INIT operation.

---

What is INIT operation ?