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

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,

*L*and_{1}*L*_{2 }such that*L*is context-free and_{1}*L*_{2 }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) 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

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?

What is the language accepted by above turing machine?

Question 6

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

- 537 attempts
- 2 upvotes
- 4 comments

Oct 6GATE & PSU CS

Posted by: