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
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
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?
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?
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
- 2 upvotes
- 4 comments
Nov 22GATE & PSU CS
