1. For DCFL,the problems which are not decidable are : a) Subset problem (Is L1 is a subset of L2?)
b) Is L1 interection L2 = phi ?(Emptiness)
c) Is intersection of two langages of same type? (DCFL intersection DCFL)?
For CFL ,the problems which are not decidable are: a) Completeness b)Equality c) Subset d) Emptiness
e) Complement is of same type or not?
f) Intersection is of same type or not?
2. Regular language : O(n)
CFL : O(np)
CSL : <= O(2n)
REC: > O(2n)
REL: Complexity not defined
3. According to me, all of them are polynomially decidable. But various places,I found that "When there are direct algorithms present , then we can say that they are polynomially decidable" . By this , only 1st option seems correct.
4. In L1/L2 , U must write few strings derivable from L1, and try to find quotient with each of the string of L2,U will definitely come across a pattern or finite number of strings.
(I hope it might help u :) )