GATE 2021 CS (CS2) – Question 51
For binary strings, $w^R$ is reversal. Which languages are context-free? w,x may be empty.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) $\{ww^Rxx^R:w,x\in\{0,1\}^*\}$; (C) $\{wxw^R:w,x\in\{0,1\}^*\}$; (D) $\{wxx^Rw^R:w,x\in\{0,1\}^*\}$
Explanation
B concatenates two even-palindrome languages, hence is context-free. C is every binary string because w can be empty and x arbitrary, so it is regular. D is an even palindrome and every even palindrome is obtainable by taking x empty, so it is context-free. A has crossing reversal dependencies and is not context-free. Select B,C,D.