Question

Consider the following languages:

I. {aᵐbⁿcᵖdᵠ | m+p=n+q, where m,n,p,q≥0}
II. {aᵐbⁿcᵖdᵠ | m=n and p=q, where m,n,p,q≥0}
III. {aᵐbⁿcᵖdᵠ | m=n=p and p≠q, where m,n,p,q≥0}
IV. {aᵐbⁿcᵖdᵠ | mn=p+q, where m,n,p,q≥0}

Which of the languages above are context-free?

Accepted Answer

The correct answer is (B) I and II only. II is clearly CFL: it's the concatenation of two independent CFLs, aⁿbⁿ and cᵖdᵖ, and CFLs are closed under concatenation. I ({m+p=n+q}) is also context-free — a linear additive relation across the fixed-order blocks can be tracked with a single stack (pushing for a's/extra-b's and popping appropriately as the c/d blocks are read), using nondeterminism to guess which side has the 'excess'. III requires matching THREE quantities (m=n=p) simultaneously, which exceeds what a single-stack PDA can enforce — not context-free (like the classic aⁿbⁿcⁿ). IV involves a MULTIPLICATIVE relation (mn), which no CFL can express (stack-based counting is fundamentally additive) — not context-free. So I and II are context-free.

Explanation