GATE CS 2018 Set 1 — Question 45

Let's analyze each language:Language I: $L_1 = \{a^m b^n c^p d^q \mid m + p = n + q\}$
The condition $m + p = n + q$ can be rewritten as $m - n = q - p$. This language is Context-Free (CFL). A Pushdown Automaton (PDA) can be constructed to accept it. For example, for the prefix $a^m b^n$, the PDA can store the difference $m-n$ on the stack. Then for the suffix $c^p d^q$, it can check if $q-p$ matches the stored difference. Alternatively, it is generated by a context-free grammar.Language II: $L_2 = \{a^m b^n c^p d^q \mid m = n \text{ and } p = q\}$
This language is the concatenation of two languages: $L_A = \{a^n b^n \mid n \ge 0\}$ and $L_B = \{c^p d^p \mid p \ge 0\}$. Since $L_A$ and $L_B$ are both standard CFLs and the class of CFLs is closed under concatenation, $L_2$ is a CFL.Language III: $L_3 = \{a^m b^n c^p d^q \mid m = n = p \text{ and } p \neq q\}$
This language requires $m=n=p$, which implies matching the counts of three different symbols ($a, b, c$). The language containing strings of the form $a^n b^n c^n$ is a well-known non-CFL. The additional condition $p \neq q$ and the presence of $d$ do not make it Context-Free. Thus, $L_3$ is not a CFL.Language IV: $L_4 = \{a^m b^n c^p d^q \mid mn = p + q\}$
The condition $mn = p + q$ involves a non-linear relationship (multiplication) between the counts of symbols. PDAs cannot perform multiplication or check such non-linear constraints generally. This language is not Context-Free.Therefore, only languages I and II are context-free.