0 votes 0 votes Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ? Theory of Computation decidability theory-of-computation context-free-language + – Shamim Ahmed asked Nov 1, 2018 • edited Dec 4, 2018 by Shaik Masthan Shamim Ahmed 520 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Verma Ashish commented Nov 1, 2018 reply Follow Share Yes emptiness problem for cfl is decidable 0 votes 0 votes Shamim Ahmed commented Nov 1, 2018 reply Follow Share How its undecidable? Can you explain it in brief? 0 votes 0 votes Verma Ashish commented Nov 1, 2018 reply Follow Share Emptiness problem for both cfg and deterministic cfg, is decidable. But here it is not asking that L(G)=Φ ? Intersection of two cfg is also a cfg. It is undecidable. And one more L1∩L2=Φ it is undecidable for cfg and det.cfg 4 votes 4 votes Please log in or register to add a comment.
