Testbook Test Series: Theory Of Computation - Grammar

Question

Comments

i is true only
http://kilby.stanford.edu/~rvg/154/handouts/ambi.html

---

i think that in(ii)      here intersection between two CFL is empty..........and i know that  emptiness problem decidable in CFG............plz tell ?? which point i wrong

---

u r right on .... emptiness problem decidable in CFG.
bt intersection of cfg need nt 2 be cfg .rt?

Answer 1

answer should be i and iii .

for regular grammar emptiness problem is decidable.

context free grammar is decidable for emptiness problem.

DCFL INTERSECTION REGULAR = DCFL (which is the subset of CFL).

hence this should also be decidable.