Question

Consider the following languages:
I. $\{a^m{b}^n{c}^p{d}^q|m+p=n+q,wherem,n,p,q\ge 0\}$
II. $\{a^m{b}^n{c}^p{d}^q|m=nandp=q,wherem,n,p,q\ge 0\}$
III. $\{a^m{b}^n{c}^p{d}^q|m=n=pandp\ne q,wherem,n,p,q\ge 0\}$
IV. $\{a^m{b}^n{c}^p{d}^q|mn=p+q,wherem,n,p,q\ge 0\}$
Which of the language above are context-free?

• A. II and IV only
• B. I and IV only
• C. II and III only
• D. I and II only

Answer 1

The correct option is D I and II only

I. $\{a^m{b}^n{c}^p{d}^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, push and pop and check if stack is empty at end.
II. $\{a^m{b}^n{c}^p{d}^q|m=nandp=q\}$ is clearly CFL since, one comparision at a time can be done by pda.
III. $\{a^m{b}^n{c}^p{d}^q|m=n=pandp\ne q\}$ is not CFL since m = n = p is a double comparision which cannot be done by PDA.
IV. $\{a^m{b}^n{c}^p{d}^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.