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 $$

$\endgroup$
2
  • $\begingroup$ Should the CFG in chomsky normal form to explain whether the language is context free? $\endgroup$
    – Lix
    Apr 27 '20 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$ Apr 27 '20 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.