Question 45

Evaluate each language:

• I. $\{a^m b^n c^p d^q \mid m + p = n + q\}$: Rewrite as $m - n = q - p$. A PDA can push $a$'s onto the stack, pop an $a$ for each $b$ (or push $b$'s if $n > m$), then push $c$'s (or cancel $b$'s), and finally match with $d$'s. Since a single stack suffices to verify the balance condition across the entire string, language I is context-free.
• II. $\{a^m b^n c^p d^q \mid m = n \text{ and } p = q\}$: This language is the concatenation of two independent CFLs: $L_1 = \{a^m b^m \mid m \ge 0\}$ and $L_2 = \{c^p d^p \mid p \ge 0\}$. Since CFLs are closed under concatenation, language II is context-free.
• III. $\{a^m b^n c^p d^q \mid m = n = p \text{ and } p \neq q\}$: Requiring three independent counts to be equal ($m = n = p$) cannot be checked by a pushdown automaton (analogous to the classic non-CFL $\{a^n b^n c^n\}$). Language III is not context-free.
• IV. $\{a^m b^n c^p d^q \mid mn = p + q\}$: Involves multiplication of counts, which cannot be recognized by any pushdown automaton. Language IV is not context-free.

Hence, only I and II are context-free, matching option B.