For A, B ⊆ Σ*, define A/B = {x ...

For A, B ⊆ Σ*, define
A/B = {x ∈ Σ* | ∃y ∈ B, xy ∈ A}
If L is a CFL and R is regular, then L/R is

(A) Regular

(B) CFL but not regular

(C) Recursive but not CFL

(D) None of the above


<div class="tex2jax"></div>

Sumit Verma sumitverma 1 Dec 2016 04:03 pm

CFL but not regular. Let P be PDA for L and M be DFA for R. Build a PDA for L/R that on input x scans x and simulates P, then when it comes to the end of the input x, guesses the string y and continues to simulate P (from the same configuration where it left off) but also runs M simultaneously on the guessed y starting from the start state. It accepts if both L and M accept. Thus it accepts its original input x if it was successfully able to guess a string y such that xy ∈ L(P) and y ∈ L(M); that is, if there exists y such that xy ∈ L and y ∈ R.

Habib Mohammad Khan habibkhan 1 Dec 2016 08:01 pm

But from closure property it follows that  L/R is a CFL ..But some CFL may be regular also..We are confirmed that the quotient or any operation will lead to say CFL but not regular only when we are given the actual language.

But the property mentioned in the question is general and hence we cannot say with surety that it will be not regular..

Hence D) should be the answer..

For B) to be correct the actual language should be given..

Let us take a counter example 

L = {an b| n > = 0}  and say since it is mentioned there exists y belongs to B so we can assume B = bn..

Thus A = an is regular and which fits into the description of the language..

Hence D) should be the correct answer..

Shobhit sudsho 2 Dec 2016 01:16 am

bhai its like saying TM also halts sometimes so it should be decidable....
if it was given that what will happen if L = {an b| n > = 0}  and R=bn then yes..answer would be regular...but here in general CFL/R=CFL only