# GATE CSE 2018, Which of the following languages are context-free?

A] {ambncpdq | m+p = n+q, where m, n, p, q >=0}

B] {ambncpdq | m = n and p = q, where m, n, p, q >=0}

C] {ambncpdq | m = n = p and p not= q, where m, n, p, q >=0}

D] {ambncpdq | mn = p+q, where m, n, p, q >=0}

Instead of Formal proofs if any answer can provide telltale signs of a language being CFL or not will be more appreciated, because this question is taken from a competitive exam. Formal proofs are welcome too.

Here is my approach

A] I don’t have any idea for constructing PDA for this language, probably not a CFL. Also by pumping lemma splitting the word in ‘uvwxy’ for any ‘vwx’ (belonging to ‘akbk‘ and such combinations), the equality won’t hold. Thus not a CFL.

B] Is a CFL we can push a’s and pop on b’s, same for c’s and d’s.

C] Not a CFL, as we need two stacks, one for keeping count of |a|==|b| and second for |b|==|c|.

D] Not a CFL, cause we can’t construct a PDA, such a PDA will require capability to move back and forth on input string (for keeping track of m*n), which is not possible.