Gate2018 cs Q50

0. Consider the following languages:
I {a^mbⁿc^pd^q | m + p = n + q, where m, n, p, q ≥ 0}
II {a^mbⁿc^pd^q | m = n and p = q, where m, n, p, q ≥ 0}
III {a^mbⁿc^pd^q | m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV {a^mbⁿc^pd^q | mn = p + q, where m, n, p, q ≥ 0}
Which of the language above are context-free?

Answer
Comment
Array

Option : B
Explanation :
I {a^mbⁿc^pd^q | m + p = n + q} is clearly CFL since, we can rearrange the equation as m - n + p - q = 0 which can be done by push, pop, and pop and check if stack is empty at end.
II {a^mbⁿc^pd^q | m = n and p = q} is clearly CFL since, one comparison at a time can be done by pda
III {a^mbⁿc^pd^q | m = n = p and p ≠ q} is not CFL since m = n = p is a double comparison which cannot be done by PDA.
IV {a^mbⁿc^pd^q | mn = p + q} is not a CFL, since mn involves multiplying number of a’s and number b’s which cannot be done by a PDA.
So, only I and II are CFL’s.

Forgot your password?

I agree with the Terms.