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

reshown Sep 8, 2019

S1 : True ,

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)

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 (14,660 points)