🔬
GATE CS - Theory of Computation
Practice finite automata, context-free grammars, Turing machines, and complexity
50 questions•5 pages•~75 min
Use this quiz track to strengthen recall, speed, and exam-style decision making. Attempt one page first, review explanations, and then re-attempt incorrect questions without notes.
A good scoring strategy is to mark uncertain questions, finish known ones quickly, and return with elimination logic. This improves accuracy while keeping momentum under time constraints.
Progress: 0 / 500%
Page 2 of 5 • Questions 11-20 of 50
Q11easy
What is the complexity class NP?
Q12medium
What is an NP-complete problem?
Q13medium
What is the language {0ⁿ1ⁿ | n ≥ 0}?
Q14medium
What is the language {0ⁿ1ⁿ2ⁿ | n ≥ 0}?
Q15medium
What is the purpose of Chomsky Normal Form (CNF)?
Q16medium
What is the difference between decidable and semi-decidable?
Q17hard
What is Rice's theorem?
Q18medium
What is the Cook-Levin theorem?
Q19easy
What is the closure property of regular languages under intersection?
Q20medium
What is the closure property of context-free languages under intersection?
...