552 views
9 votes
9 votes
$D_1$ and $D_2$ are Deterministic Pushdown Automata and $E$ is a Finite Automaton. Which of the following problems is/are decidable? (Mark all the appropriate choices)
  1. Is $L(D_1)\cap L(D_2)$ a Deterministic-CFL?
  2. Is $L(D_1)\cap L(D_2) = \emptyset?$
  3. Is $L(D_1)\subseteq L(E)?$
  4. Is $L(E)\subseteq L(D_1)?$

1 Answer

Best answer
14 votes
14 votes

DCFLs are not closed under intersection. (In fact, when we intersect two DCFLs we can get a non CFL also). Now, even for CFLs, checking if it is a DCFL is undecidable. So, A is undecidable.

Same as above, checking if a CFL is empty is decidable but after intersecting two DCFLs we can get a CSL which may not be a CFL. And checking whether a CSL is empty is undecidable.

$L(D_1)\subseteq L(E)$ is same as $L(D_1)\cap L(E)^c = \emptyset.$ $L(E)^c$ is regular since regular set is closed under complement and DCFLs (even CFLs) are closed under intersection with a regular language reducing our problem to checking if a DCFL is empty which is decidable.

$L(E)\subseteq L(D_1)$ is same as $L(D_1)^c\cap L(E) = \emptyset$ and like above this reduces to checking if a DCFL is empty which is decidable.

So, correct options: C;D

Reference: https://gatecse.in/grammar-decidable-and-undecidable-problems

selected by
Answer:

Related questions