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$ Commented Dec 7, 2012 at 6:10
  • $\begingroup$ Ok, i'll show my work $\endgroup$ Commented Dec 7, 2012 at 6:11
  • 1
    $\begingroup$ Now can you argue (perhaps informally) why your grammar is correct? $\endgroup$ Commented Dec 7, 2012 at 6:14
  • $\begingroup$ alright. i'll add more. done. $\endgroup$ Commented Dec 7, 2012 at 6:16
  • 4
    $\begingroup$ You are right. Please post your thoughts as self-answer to you question. $\endgroup$
    – A.Schulz
    Commented 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 you have read our privacy policy.

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