Back to the 2023 paper

Module 2: Context-Free Languages (CFL) and PDA

20232m

Which one of the following statements is true?

(i) The intersection of two CFLs is context-free
(ii) Every CFL can be accepted by a DPDA
(iii) The union of two CFLs is context-free
(iv) The complement of a CFL is context-free

Worked SolutionAI Assisted

Answer

Correct Option: (iii) The union of two CFLs is context-free

Explanation

CFL closure:

Operation Closed? Example
Union L1∪L2L_1 \cup L_2 Yes S→S1∣S2S \rightarrow S_1 \mid S_2
Intersection L1∩L2L_1 \cap L_2 No anbnc∗∩a∗bncn=anbncna^n b^n c^* \cap a^* b^n c^n = a^n b^n c^n not CFL
Complement No Follows from De Morgan
Every CFL is DPDA No {anbn}∪{anb2n}\{a^n b^n\} \cup \{a^n b^{2n}\} is CFL but not DCFL
Intersection of 2 CFLs is CFL No

Thus only union is guaranteed.

Options:

  • (i) Intersection → false
  • (ii) Every CFL is DPDA → false (DCFL ⊂ CFL)
  • (iii) Union → true ✓
  • (iv) Complement → false

Final Answer

Union of two CFLs is CFL → Option (iii).

Similar questions

Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.