Time Left - 15:00 mins

GATE CS 2021 : Theory of computation Quiz 7 (App update required to attempt this test)

Attempt now to get your rank among 555 students!

Question 1

The transition diagram for a TM is shown below:

Here: B Blank
X, Y: tape alphabets
R Move right
L Move left
Which of the following strings can be simulated by the above TM

Question 2

For any two languages, L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

Question 3

Consider the following languages
A= {<M> | TM ‘M’ accepts atmost 2 distinct inputs}
B= {<M> | TM ‘M’ accepts more than 2 distinct inputs}
Identify the correct statement from the following

Question 4

Consider the following problems:
A) If A is a recursive language, then A’ is also recursive
B) If A is a regular language, then A’ is also regular
C) If A is a recursive enumerable language, then A’ is also recursive enumerable
D) If A is context-free, then A’ is also context-free
Which one of the above problems is decidable?

Question 5

Consider the following transition table of the Turing machine.

What is the language accepted by the above Turing machine?

Question 6

Minimum number of stacks required by PDA to behave like TM?
  • 555 attempts