Time Left - 20:00 mins

GATE CS : Theory of Computation Champion Quiz 3

Attempt now to get your rank among 519 students!

Question 1

Which of the following is CFL but not DCFL

Question 2

Let L = {(a^p)^* | p is a prime number} and How many minimum number of states in NFA that accepts a language L?

Question 3

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Question 4

Let L denotes the language generated by the grammar S →0S0/00.Which of the following is true?

Question 5

Which of the following statements are true?

Question 6

Definition of a language L with alphabet {a} is given as following.
L= {a^nk | k>0, n is positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?

Question 7

Define languages L₀ and L₁ as follows:
L₀ = {<M, w, 0> | M halts on w}
L₁ = {<M, w, 1> | M does not halt on w}
Here <M, w, i> is a triplet, whose first component, M, is an encoding of a Turing
Machine, second component, w, is a string, and third component, i, is a bit.
Let L = L₀∪ L₁. Which of the following is true?

Question 8

The language, {a^mbⁿc^m+n|m,n ≥1} is

Question 9

Consider the following languages.
L₁={0^p 1^q 0^r | p, q, r > 0}
L₂={0^p 1^q 0^r | p, q, r > 0, p ≠ r }
Which one of the following statements is FALSE?

Question 10

Consider the languages

Which one of the following statements is true?

519 attempts
3 upvotes
30 comments

Tags :

GATE & PSU CS Theory of Computation

Apr 2GATE & PSU CS