GATE CS 2021 Set 2 Q41 — Context-free Grammars and Push-down Automata

To determine which of the languages are context-free, we analyze each option:

• Option A: $L_A = \{ wxw^Rx^R \mid w,x \in \{0,1\}^* \}$. This language requires matching $w$ with $w^R$ and $x$ with $x^R$ in an overlapping (cross-serial) manner. A single pushdown stack cannot handle two overlapping LIFO comparisons simultaneously. Thus, $L_A$ is not context-free.
• Option B: $L_B = \{ ww^Rxx^R \mid w,x \in \{0,1\}^* \}$. This is the concatenation of two standard context-free languages: $L_1 = \{ ww^R \mid w \in \{0,1\}^* \}$ and $L_2 = \{ xx^R \mid x \in \{0,1\}^* \}$. Since context-free languages are closed under concatenation, $L_B$ is context-free.
• Option C: $L_C = \{ wxw^R \mid w,x \in \{0,1\}^* \}$. If we choose $w = \epsilon$, then $wxw^R = x$. Since $x \in \{0,1\}^*$, any string in $\{0,1\}^*$ can be represented in this form. Thus, $L_C = \{0,1\}^*$, which is a regular language and therefore context-free.
• Option D: $L_D = \{ wxx^Rw^R \mid w,x \in \{0,1\}^* \}$. Let $y = wx$. Then $y^R = (wx)^R = x^Rw^R$. Thus, the language is equivalent to $\{ yy^R \mid y \in \{0,1\}^* \}$, which is the classic even-length palindrome language and is context-free.

Therefore, options B, C, and D are context-free.