# Is this a Context Free Language?

I got this question on my final exam: Is the following language context-free?

$$L = \{w\bar w^R \mid w\in \{0,1\}^* \}$$

Notation: The string $\bar w$ is obtained from $w$ by replacing all 0s with 1's and all 1's with 0's. The string $\bar w^R$ is $\bar w$ in reverse order.

I've thought about it being a context-free language, but I notice that when you pump the string in the middle, the string will still be in the language. (using pumping lemma)

I think it's context free. This is the context free grammar:

$$S \to 0S1 \mid 1S0 \mid \varepsilon$$ (It's basically a palindrome, but both sides are exact opposites.)

-
What do you think? What have you tried to show that it is? Or that it isn't? – Dave Clarke Dec 7 '12 at 6:10
Ok, i'll show my work – Jessie Love Dec 7 '12 at 6:11
Now can you argue (perhaps informally) why your grammar is correct? – Luke Mathieson Dec 7 '12 at 6:14
alright. i'll add more. done. – Jessie Love Dec 7 '12 at 6:16
You are right. Please post your thoughts as self-answer to you question. – A.Schulz Dec 7 '12 at 7:43