Question:medium

Match List - I with List - II. 

List - IList - II
A.Cook's TheoremI.The Boolean satisfiability problem (SAT) is NP-complete
B.Pumping lemma for regular languagesII.Used to prove non-regularity of certain languages
C.Closure under complementationIII.Fails for context-free languages
D.Non-deterministic pushdown automataIV.Recognises all context-free languages

Choose the correct answer from the options given below:

Show Hint

Remember the "Not-Closed" list for CFLs: Intersection and Complementation. If a question asks what fails for CFLs, check for those two!
Updated On: Jun 8, 2026
  • A-I, B-II, C-III, D-IV
  • A-II, B-I, C-III, D-IV
  • A-III, B-II, C-IV, D-I
  • A-IV, B-III, C-II, D-I
Show Solution

The Correct Option is A

Solution and Explanation

Was this answer helpful?
0

Top Questions on Theory of Computations

Questions Asked in CUET (PG) exam