August 22, 2023
August 22, 2023
August 22, 2023
###### GATE 2021 CS-Set-2
August 22, 2023
 Question 13
For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR= 10110.

Which of the following languages is/are context-free?

 A L={w x wR xR | w, x ∈ {0,1}* } B L={w wR x xR | w, x ∈ {0,1}* } C L={w x xR wR | w, x ∈ {0,1}* } D L={w x wR | w, x ∈ {0,1}* }
Question 13 Explanation:

Option A: L={w x wR  xR  | 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 wR x xR  | 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  xR wR   | 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  wR   | 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).

Question 13 Explanation:

Option A: L={w x wR  xR  | 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 wR x xR  | 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  xR wR   | 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  wR   | 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).