1
$\begingroup$

I came across following problem:

Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any language, then what is the smallest language family $L'$ belongs to?

I know DCFLs are not closed under set difference operation. Neither do CFL are closed. However CSLs are closed under set difference operation. So $L$ must be CSL. CSLs are also closed under complementations. Thus, $L'$ must be CSL. But when checked the solution, it gave $L'$ must be recursive. The reason given was:

If CFL $\cap$ CFL is accepted in time complexity $\leq O(2^n)$,then $L'$ will be CSL. If it is accepted in time complexity $>O(2^n)$, then it will be recursive.

However I dont really get what does this means. I have never used time complexity logic to decide which language family given language belongs to. Can someone explain? Also if that does means something, isnt it wrong to say CSLs are closed under intersection and complementation? Why we have to disregard CSL bound can call them recursive?

$\endgroup$
  • $\begingroup$ "CFLs are closed under set difference operation" -- that sounds wrong. If that were the case, CFLs would also be closed under complementation (which is a special case of difference). $\endgroup$ – chi Dec 26 '17 at 10:05
  • $\begingroup$ noticed stupid mistake I did while asking question in hurry. Edited the question now. Thanks. $\endgroup$ – anir Dec 26 '17 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.