Time Left - 30:00 mins

GATE CS 2021 : Theory of computation Rapid Mini Mock (App update required to attempt this test)

Attempt now to get your rank among 913 students!

Question 1

A student want to prove a relation between the “gradeup” and “gaterank”. If he prove that gradeup is reducible to “gaterank” and “gaterank” is decidable then which of the following is true? (Assume gradeup & gaterank are two problems)

Question 2

Which of the following problems is undecidable? 

Question 3

Recursive language is not closed under which operation?

Question 4

Which of the following CFG generates a regular language?

Question 5

Any string of terminals that can be generated by the following CFG satisfy which of the given choices?
S XY
X aX | bX | a
Y Ya | Yb | a

Question 6

Regular Languages are closed under:

Question 7

Which of the following languages is (are) non-regular? L1 = {0m1n | 0 ≤ m ≤ n ≤ 10000} L2 = {w | w reads the same forward and backward} L3 = {w {0, 1} * | w contains an even number of 0's and an even number of 1's}

Question 8

Give the R.E described by the following NFA.

Question 9

Considerthe following DFA that accepts a language L over

Which of the following represents the complement of a language L?

Question 10

Consider the following identities. Choose the wrong one

Question 11

What is following regular expression represent:

{ ( b* a b* a b* a b* )* + b* } ( ab* + ab*ab*)

here n(a) represent number of a’s and n(b) represent number of b’s .

Question 12

The minimum possible number of states of a deterministic automaton that accepts the regular language L = {w1aw2 | w1, w2 {a,b}*, |w1|=2,|w2|≥3} is _____.
  • 913 attempts
  • 5 upvotes
  • 14 comments
Dec 14GATE & PSU CS

Posted by:

Harshita AgarwalHarshita AgarwalMember since Jul 2020
Share this quiz   |