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

Question

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.

Answer 1

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