Time Left - 10:00 mins

GATE 2020 : Theory of Computation Quiz 6

Attempt now to get your rank among 675 students!

Question 1

When does a PDA behaves like a Turing machine ?

Question 2

Let L1 be a recursive language and L2 be a recursive enumerable language. Then L2 – L1 is?

Question 3

A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table.

The table is interpreted as illustrated below.
The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1.
Which of the following statements is true about M?

Question 4

Consider the following statements about the Turing machine
1. It can be represented using instantaneous description
2. In one move the Turing machine can write a symbol on the cell being scanned
3. It can be represented using transition table
Which one of the above statements is true?

Question 5

Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation.
(4) Turing recognizable languages are closed under union and intersection.

Question 6

Write the transition rule for the code
0001000100010010
  • 675 attempts
  • 5 upvotes
  • 3 comments
Jul 14GATE & PSU CS