TOC-grand test-Q13

Question

Consider the following statements

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

S2 : If and are regular languages, then is regular as well.

S3 : if 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..... the union 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

Answer 1

S1 : True , 

 

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

 

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

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

Answer 2

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