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


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 following statements

S1 : Turing-recognizable languages are closed under the prefix operation.

S2 : If \small A \cap B, B \cap C, and \small A \cap C are regular languages, then \small A \cup B \cup C is regular as well.

S3 : if \small C\cup F is context-free and F is finite, then C is context-free.

S4 : For DPDA acceptance with empty stack and acceptance with Final State are not equivalent. But for a NPDA Final-state acceptance and empty-stack acceptance are equivalent.

S5 : For any regular languages\small L_{1} \subseteq L_{2} \subseteq L_{3}\subseteq..... the union \small L=\bigcup_{n=1}^{\infty }L_{n} is regular

Which of the above statement(s) are INCORRECT ?

(A) S1 and S2

(B) S4 and S5

(C) S2 , S3 and S5

(D) S2 and S5

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

2 Answers

0 votes
 
Best answer

S1 : True , 

image

 

S2 : False. Let A be any nonregular language, and let B = C = \phi. Then the pairwise intersections A \cap B = B \cap C = C \cap A = \phi are regular, but the union A \cup B \cup C = A is nonregular.

 

S3 : True, Suppose that C ∪ F is context-free and F is finite. We have

C = ( C \cup F) - (F - C) = ( C \cup F ) \cap ( F - C )^c

The language C ∪F is context-free by assumption. The other language, (F - C)' , is regular by the closure properties because it is the complement of the finite (hence regular!) language F-C. Therefore, C is the intersection of a context-free language and a regular language. Which is context free.

 

S4 : True , For DPDA acceptance with empty stack and acceptance with Final State are not equivalent. In the case of DPDA, acceptance by the empty stack is weaker, since the language has to satisfy the prefix property.It can also be said that set of languages accepted by a DPDA by empty stack is the set of languages accepted by a DPDA by final state and which has the prefix property. 

 

Note : A DPDA with acceptance by empty stack cannot even accept all regular languages- example a∗.

 

But for a NPDA Final-state acceptance and empty-stack acceptance are equivalent.

 

S5 : False. Regular Languages are not closed under infinite union.

 

Hence Option D

answered Sep 11, 2019 by (91,540 points)
+2 votes

ANS D.

S5- Infinite union of RL is not closed thus can or can be NOT RL. So it incorrect.

S2- False, Not need to be RL. 

S3- True. as F is finite so it is RL. Cfl union Rl is CFL. 

S1- True.

S4- True 

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