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 537 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) Does a given program ever produce an input?
D) If A is context-free, then A’ is also context-free?
Which one of the above problems are decidable

Question 5

Consider the following transition table of turing machine.

What is the language accepted by above turing machine?

Question 6

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

Posted by:

Harshita AgarwalHarshita AgarwalMember since Jul 2020
Share this quiz   |