3
$\begingroup$

Is the language $\{ w=w^R \mid w \in \{0,1\}^* \}$ a context-free language?

I am confused in deciding whether the language is context-free or not, that is one of my problems, I do a pumping lemma proof and what I get is that it is not a context-free language, but I want to make sure again.

$\endgroup$
2
$\begingroup$

The language of palindromes is one of the standard examples of a non-regular context-free language. It is generated by the context-free grammar $$ S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \epsilon $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Should the CFG in chomsky normal form to explain whether the language is context free? $\endgroup$ – Lix Apr 27 at 7:42
  • $\begingroup$ No. It is well-known that any language described by a context-free grammar is context-free. Indeed, many people define context-free languages this way. $\endgroup$ – Yuval Filmus Apr 27 at 7:43

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.