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$ – Dave Clarke Dec 7 '12 at 6:10
  • $\begingroup$ Ok, i'll show my work $\endgroup$ – Jessie Love Dec 7 '12 at 6:11
  • 1
    $\begingroup$ Now can you argue (perhaps informally) why your grammar is correct? $\endgroup$ – Luke Mathieson Dec 7 '12 at 6:14
  • $\begingroup$ alright. i'll add more. done. $\endgroup$ – Jessie Love Dec 7 '12 at 6:16
  • 4
    $\begingroup$ You are right. Please post your thoughts as self-answer to you question. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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