• Register
    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 580

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
  • Questions
    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 580
  • Unanswered
    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 580
  • Tags
    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 580
  • Categories
    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 580
  • Users
    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 580
  • Exams Taken
    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 580
  • Exam List
    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 580

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

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

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

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

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

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)?

asked Sep 7, 2019 by gbeditor-2 (72,840 points)
reshown Sep 8, 2019 by gbeditor-2

1 Answer

+1 vote
 
Best answer

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 ifL(G) \cap compl(L(R)) is \phi)

Hence Option D

answered Sep 8, 2019 by bhargavakapilpro20 (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?
Answer:

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

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

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
...