Virtual Gate Test Series: Theory Of Computation - Languages

Question

For $A,B\subseteq \Sigma ^{*},$ define

$A/B=\{x\in\Sigma^{*}\mid \exists y\in B,xy\in A\}$

If $L$ is a $\text{CFL}$ and $R$ is $\text{Regular},$ then $L/R$ is$?$

1. Regular
2. CFL but not Regular
3. Recursive but not CFL
4. None of the above

Comments

pls confirm the answer .....

Answer 1

Consider L as any CFL [say ww^r] and choose R = {ϵ} [as R is given Regular in question]

So Now for all x in L, there exist y i.e ϵ such that xy ϵ L [as xy = xϵ = x and x is in L only]. So L/R is nothing but L itself. 

Hence L/R is CFL and hence recursive too [so option c is false]

Only correct option is B.

Comments

@Gate Mission 1, these types of qsns can't be evaluated on the basis of particular example..

---

what if, L={aⁿbⁿ}   

and R={b*}

 then L/R will be {a*} which is regular

---

@Magma @srestha @Shaik Masthan

None of above should be ans??

it might be Regular or CFL.?

---

CFL quetionent with RL = CFL

( Note that every RL is CFL )

---

@Shaik Masthan

it might be regular too but as CFL already contain Regular so B can be option?

---

yes