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?
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?
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?
Which of the following statements is true?
- 441 attempts
- 1 upvote
- 3 comments
Jul 20GATE & PSU CS