• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Theory of Computation

Which of the following statements is true? A. If a language is context free it can always be accepted by a deterministic push-down automaton B. The union of two context free languages is context free C. The intersection of two context free languages is context free D. The complement of a context free language is context free

GATE 2001 · Theory of Computation · Context Free Language · easy

Answer: Option B is true: The union of two context free languages is context free.

  1. Evaluate option A: Option A says every CFL can be accepted by a DPDA. This is FALSE. There exist CFLs that are inherently nondeterministic (e.g., {ww^R | w in {a,b}*} cannot be accepted by any DPDA, yet it is CFL).
  2. Evaluate option B: Option B says the union of two CFLs is a CFL. This is TRUE. Proof: if G1 = (V1, T1, P1, S1) and G2 = (V2, T2, P2, S2) generate L1 and L2, create G = (V1 union V2 union {S}, T1 union T2, P1 union P2 union {S->S1, S->S2}, S). Then L(G) = L1 union L2.
  3. Evaluate options C and D: Option C: Intersection of two CFLs is CFL — FALSE. Counterexample: L1 and L2 above are CFLs but L1 ∩ L2 = {a^n b^n c^n} is not CFL (provable by pumping lemma for CFLs). Option D: Complement of a CFL is CFL — FALSE. If both intersection and complement were closed, CFLs would be closed under intersection (by De Morgan: L1 ∩ L2 = complement(complement(L1) union complement(L2))), contradicting C.