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



sumitverma's picture

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.

habibkhan's picture

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..

sudsho's picture

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

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form


Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.