patternMinor
Is the language of palindromes context-free?
Viewed 0 times
thepalindromesfreelanguagecontext
Problem
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.
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.
Solution
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
$$
$$
S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \epsilon
$$
Context
StackExchange Computer Science Q#124662, answer score: 2
Revisions (0)
No revisions yet.