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

  • $\begingroup$ Please show what you tried, where exactly you see yourself stuck. $\endgroup$ – greybeard Jun 1 '20 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$"

  • basis is simple. Do it yourself.
  • 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$

  • $\begingroup$ thank you so much kind person $\endgroup$ – Katerina May 30 '20 at 22:53
  • $\begingroup$ no problem. This is the reason StackExchange exists in the first place :) $\endgroup$ – nir shahar May 30 '20 at 22:58

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.