Time Left - 10:00 mins

Mission ISRO 2017 Day-15: Theory of Computation Quiz-2

Attempt now to get your rank among 441 students!

Question 1

Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?

Question 2

An FSM (Finite State Machine) can be considered to be a TM (Turing Machine) of finite tape length

Question 3

A problem whose language is recursion is called?

Question 4

If L and L’ are recursively enumerable, then L is

Question 5

G = {S SS, S ab, S ba, S ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. Language of G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?

Question 6

Choose the correct statement among the following?

Question 7

Which of the following problems is undecidable? 

Question 8

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B*. We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language Which of the following statements is true:

Question 9

Let X be a recursive language and Y be a recursively enumerable but not recursive language.
Let W and Z be two languages such that W = ¬X and Z = ¬Y  Which one of the following statements is TRUE?

Question 10

Nobody knows yet if P = NP. Consider the language L defined as follows.

Which of the following statements is true?
  • 441 attempts
  • 1 upvote
  • 3 comments
Jul 20GATE & PSU CS