Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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