GATE CSE 2021 Set 2 Q51: Which reversal-based languages are context-free

For a string $w$ , we define $w^R$ to be the reverse of $w$ . For example, if $w = 01101$ then $w^R = 10110$ .

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

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, C, D (official GATE 2021 final answer key)

Concept used: A single stack can match nested (properly bracketed) pairs but not crossing pairs.

First step: Draw arcs matching $w$ with $w^R$ and $x$ with $x^R$ : they nest or sit side by side in B, C, D, but cross in A.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key