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 950 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
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}
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?
Which of the following represents the complement of a language L?
Question 10
Consider the following identities. Choose the wrong one among the given options.
Question 11
What does 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 _____.
- 950 attempts
- 5 upvotes
- 14 comments
Aug 22GATE & PSU CS
