Time Left - 20:00 mins

GATE CS : Theory of Computation Champion Quiz 4

Attempt now to get your rank among 511 students!

Question 1

Recursively enumerable language (problem) is ___________

Question 2

Consider the following unrestricted grammar.

What is the language generated by above grammar?

Question 3

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 4

Which of the following pairs have DIFFERENT expressive power?

Question 5

If L and

are recursively enumerable then L is

Question 6

Consider the machine M:

The language recognized by M is:

Question 7

L₁ is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as ω₁, ω₂, ω₃, …… define another language L₂ over Σ ∪ {#} as {ω_i # ω_j : ω_j ∈ L₁, i < j}. Here # is a new symbol. Consider the following assertions.
S₁ : L₁ is recursive implies L₂ is recursive
S₂ : L₂ is recursive implies L₁ is recursive
Which of the following statements is true?

Question 8

Consider the following decision problems:
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Which of the following statements is true?

Question 9

Which of the following language is recursively enumerable language?

Question 10

Find the grammar that generates an inherently ambiguous context free language.

511 attempts
1 upvote
28 comments

Tags :

GATE & PSU CS Theory of Computation

Apr 2GATE & PSU CS