Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

TOC-grand test-Q5

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

For arbitrary CFGs G, G1 and G2 and an arbitrary regular expression R. Which of the following is DECIDABLE ?

(A) Whether $\small L(G1) \cap L(G2)$ is a DCFL ?

(B) Whether $\small L(G) = L(R)$ ?

(C) Whether $\small L(R) \subseteq L(G)$ ?

(D) Whether $\small L(G) \subseteq L(R)$?

reshown Sep 8, 2019

+1 vote

It can be arbitrary CFG so it can be CFL OR DCFL.

Option A is UD as CFL and DCFL both are NOT closed under Intersection.

Option B. It is also UD as for CFL, equivalence prob is UD.

Option C is undecidable

Option D is DECIDABLE

Whether  $L(G) \subseteq L(R)$ is decidable. (We can test if$L(G) \cap compl(L(R))$ is $\phi$)

Hence Option D

answered Sep 8, 2019 by (14,660 points)
edited Sep 12, 2019 by
( R  ⊆ G ) we need to get ( R ∩ G'= Φ ).

R ∩ G' i.e. Regular ∩ CFL = CFL we know.

And whether CFL=Φ is decidable (If no string can be generated from the CFG then it is NULL and that can be checked from it's grammar. Hence decidable).
so why not option c??
If we apply rice theorem i.e non trivial property
Then options b,c,d satisfy  non trivial property so this they can't be decidable.
Am I correct?