Question

Match List - I with List - II. 

List - I		List - II
A.	Cook's Theorem	I.	The Boolean satisfiability problem (SAT) is NP-complete
B.	Pumping lemma for regular languages	II.	Used to prove non-regularity of certain languages
C.	Closure under complementation	III.	Fails for context-free languages
D.	Non-deterministic pushdown automata	IV.	Recognises all context-free languages

Choose the correct answer from the options given below:

• A. A-I, B-II, C-III, D-IV
• B. A-II, B-I, C-III, D-IV
• C. A-III, B-II, C-IV, D-I
• D. A-IV, B-III, C-II, D-I

Hint:

Remember the "Not-Closed" list for CFLs: Intersection and Complementation. If a question asks what fails for CFLs, check for those two!

Answer 1

The Correct Option is A

Concept:
• Theory of computation deals with the complexity of problems and the characteristics of different language classes (Regular, Context-Free, etc.).

Step 1: Identify Cook's Theorem (A-I)
Cook's Theorem is a cornerstone of complexity theory. It proved that the Boolean Satisfiability Problem (SAT) is NP-complete, providing the first known member of this class.

Step 2: Identify Pumping Lemma usage (B-II)
The Pumping Lemma provides a necessary condition that all regular languages must satisfy. It is typically used as a tool for proof by contradiction to show that a specific language is not regular.

Step 3: Identify CFL Closure properties (C-III)
Context-Free Languages (CFL) are closed under Union, Concatenation, and Kleene Star. However, they are notably not closed under Intersection or Complementation. Thus, closure under complementation fails for CFL.

Step 4: Identify the power of NPDA (D-IV)
A Non-deterministic Pushdown Automaton (NPDA) is exactly the machine that accepts the class of Context-Free Languages. Note that Deterministic PDAs only accept a subset (DCFL).