# Proof for palindrome grammar by induction

I can't seem to find a solution to the following question.

Given the following grammar for palindromes:
$$G_{pal}=\{\{a,\dots,z\},\{P\},P,R\},$$ with $$R$$ consisting of the rules
$$P \to \epsilon \mid a \mid aPa\text{ for every }a \in \Sigma.$$

Prove that every palindrome $$w$$ is in $$L(G_{pal})$$:

$$w = w^r \longrightarrow w \in L(G_{pal}).$$

• Please show what you tried, where exactly you see yourself stuck. – greybeard Jun 1 at 5:00

To show $$w\in L(G_{Pal})$$, Show with induction on word length the lemma: "If $$w=w^R$$ then $$P\rightarrow...\rightarrow w$$"
• assume $$|w|=n+1$$ and we know that every $$\hat w$$ with $$\hat w = \hat w^R, |\hat w|\le n$$ satisfies, $$P\rightarrow...\rightarrow \hat w.$$ Then: define $$\hat w:=w_{2,...,n}$$. since $$w=w^R$$ then also $$\hat w = \hat w^R$$. But $$|\hat w|\le n$$, thus $$P\rightarrow...\rightarrow \hat w$$. Now we can derive $$w$$ since we know we can derive $$w'$$: $$P\rightarrow w_1Pw_1\rightarrow w_1Pw_{n+1}\rightarrow...\rightarrow w_1\hat ww_{n+1}=w$$
We have shown that $$w$$ can be constructed from $$P$$ in the grammer. So $$w=w^R\rightarrow w\in L(G_{Pal})$$
Note that in order to show that this grammer is correct, this is not enough. you will need to also show that $$w\in L(G_{Pal})\rightarrow w=w^R$$