• 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-Q11


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

Consider the computational problems about the context free languages given below.

P1 : on input a PDA, determine if the height of its stack exceeds 2019 in any computation.

P2 : on input a context-free grammar, determine if it generates infinitely many strings in \small 1^*

P3 : on input a PDA P; determine if P can ever enter an accept state with its stack empty;

P4 : on input a context-free grammar G; determine if L(G) is finite.

Which of the above problems are UNDECIDABLE ?

(A) Only P4

(B) P2 and P3

(C) P1 and P4

(D) None of them

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

2 Answers

0 votes
 
Best answer

P1 : DECIDABLE

 

Let P be a given PDA. Modify P to keep track of the maximum stack height so far, the possibilities being 0,1,..,2019,2019+. This added functionality can be implemented as part of the state. Modify the automaton further to accept its input iff the maximum stack height so far is 2019+. Finally, use the algorithm from class to check whether the resulting PDA accepts any strings.

 

P2 : DECIDABLE

 

image

 

P3 : DECIDABLE

 

image

 

P4 : DECIDABLE

 

image

Hence Option D

answered Sep 11, 2019 by (91,540 points)
selected Sep 12, 2019 by
0 votes

ANS D

P4-  Finiteness prob of cfl is Decidable. 

P3- Decidable, Membership prob. 

P1- Decidable .

P2- Decidable 

answered Sep 8, 2019 by bhargavakapilpro20 (14,660 points)
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
...