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.)

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

1 Answer 1


A Context free grammer is one in which LHS of atleast one of the productions is free from any terminal symbols (context). According to your production rule,it is clearly CFG.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.