GATE CSE Turing Machines, RE Languages & Undecidability – TOC Practice Test

GATE CSE Turing Machines, RE Languages & Undecidability – TOC Practice Test | Set 1

Questions 31-35 of 100

0% completed (0/100 answered)

Question 31

MCQ · Single Correct 1 mark

Which hierarchy relation is correct?

A REG ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE B REG ⊂ CFL ⊂ DCFL ⊂ CSL ⊂ RE ⊂ REC C REC ⊂ RE ⊂ CFL D CFL ⊂ REG

MCQ · Single Correct 1 mark

Which statement about context-sensitive languages is correct?

A They are not closed under intersection B They are closed under complement C They are all nonrecursive D They equal regular languages

MCQ · Single Correct 1 mark

Which of the following is not a semantic property of L(M)?

A L(M) is finite B L(M) is regular C M has exactly 8 states D $L(M) contains \epsilon$

MCQ · Single Correct 1 mark

Which problem for TMs is recognizable but not decidable?

A Does M have 3 states? B Does M use symbol X? C Does the description contain q0? D Does M halt on w?

MCQ · Single Correct 1 mark

If both L and its complement are recursively enumerable, then L is:

A Recursive B Regular C Context-free D Undecidable