# 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? Dec 7, 2012 at 6:10
• Ok, i'll show my work Dec 7, 2012 at 6:11
• Now can you argue (perhaps informally) why your grammar is correct? Dec 7, 2012 at 6:14
• alright. i'll add more. done. Dec 7, 2012 at 6:16
• You are right. Please post your thoughts as self-answer to you question. Dec 7, 2012 at 7:43