# Proof verification of the language of all palindromes as being context-free

Consider that the language L of all palindromes over $$\Sigma = \{0,1\}^*$$ is not context-free. The following is my attempt at a proof by contradiction.

I am new to proof writing and I am wondering if the proof is correct, and if it proceeds in a connected logical sequence. I think I have all the cases covered, but I am not too sure.

• Could you explain why $uwy = 0^k1^{2k}o^k$? If I set $w = 1, v = x = 1$, then neither $x$ nor $v$ equals $\epsilon$, $|vwx| < p$ and $uv^iwx^iy \in L$, but $uwy$ is not of the form you state. Apart from that, there's a very simple grammar for palindromes: $w := "" | "1" | "0" | "1" w "1" | "0" w "0"$ that looks pretty context free to me – Ronald Dec 6 '18 at 0:33
• @Ronald could you elaborate? Are you saying that the language of palindromes is context free? – SeesSound Dec 6 '18 at 1:02

If a context free grammar exists that produces the language, then the language itself is context free.

A context free grammar is a 4-tuple $$G = (V, \Sigma, R, S)$$ with the following properties:

1. $$V$$ is a finite set; $$v \in V$$ is called a non-terminal symbol
2. $$\Sigma$$ is a finite set of terminal symbols; $$V \cap \Sigma =\emptyset$$
3. $$R$$ is a finite relation $$V \rightarrow (V \cup \Sigma)^*$$
4. $$S \in V$$ is the start symbol

With $$V = \{w\}$$, $$\Sigma = \{0, 1\}$$, $$S = w$$ and the following map $$R$$:

$$w \rightarrow \epsilon$$
$$w \rightarrow 0$$
$$w \rightarrow 1$$
$$w \rightarrow 0w0$$
$$w \rightarrow 1w1$$

we've defined a context free grammar.

Note: if the empty string isn't considered to be a palindrome, the first production can be replaced by

$$w \rightarrow 00$$
$$w \rightarrow 11$$

Palindromes are, casually speaking, a special case of "well-formed parenthesis" (each opening parenthesis has a corresponding closing parenthesis) which is also known to be context free.

Context free languages can't "count" very well, but it isn't a problem to have an arbitrary number of matching pairs as this can be tested using a stack. But the famous language $$a^nb^nc^n$$ isn't context free because there's no way to count to $$n$$.

Edit:
Strictly speaking I'll have to prove that the above grammar indeed produces the set of all palindromes.

First of all, if $$w \in L$$, which means that $$w$$ is a palindrome, then also $$0w0$$ and $$1w1$$ are palindromes and therefore member of $$L$$. Obviously $$0, 1$$ and $$\epsilon$$ are palindromes.
In other words, the production rules only produce palindromes.

Now assume $$p$$ is a palindrome. Then $$p = s_1s_2...s_nms_ns_{n-1}...s_1$$, with $$s_i \in \{0, 1\}, i \in \{1, ..., n\}$$ and $$m \in \{\epsilon, 0, 1\}$$.

In order to produce this palindrome, we start with $$w = m$$ and then consecutively add the symbols $$s_n, s_{n-1}, ..., s_1$$ on either side of $$w$$, which is allowed by the last two production rules.

This proves that $$p$$ can be produced by the grammar above.
Together with the fact that $$G$$ produces palindromes only, this proves that $$G$$ is a valid grammar for $$L$$.