# Why is the language of even-length non-palindromes context-free?

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language.

Can anyone help me produce a PDA or give me any hint how I can quickly understand why this is context-free?

• What have you tried and where did you get stuck? Can you construct a PDA for the set of (equal-length) palindromes? – Raphael Aug 11 '14 at 21:01
• Then you are already 95% of the way there. – Raphael Aug 11 '14 at 21:16

$$S \rightarrow 0S0 \mid 1S1 \mid D$$ $$D \rightarrow 1A0 \mid 0A1$$ $$A \rightarrow \lambda \mid 00A \mid 01A \mid 10A \mid 11A$$