GATE 2021 CS-Set-2

Option A: L={w x w^R  x^R  | w, x ∈ {0,1}* }

This is not CFL as if we push “w” then “x” then we cannot match wR with “w” as top of stack contains x.

Option B: L={w w^R x x^R  | w, x ∈ {0,1}* }

This is CFL. We non deterministically guess the middle of the string. So we push “w” then match with wR  and again push x and match with xR  

Option C: L={w x  x^R w^R   | w, x ∈ {0,1}* } 

This is also CFL. We non deterministically guess the middle of the string. So we push “w” then push x and then  match with xR  and again match with wR 

Option D: L={w x  w^R   | w, x ∈ {0,1}* }

This is a regular language (hence CFL). In this language every string start and end with same symbol (as x can expand).