Parsing

Let $=\{a,b,c\}$ be the alphabet. A palindrome over $$ is a string $w,$ such that $|w|0$ and

such that $w=w^{-1},$ e$.$g$.,$ it reads the same from left to right and from right to left.

Examples are:

abba

abccba

aca

where as abab is not a palindrome.

$[6/39]$ Write a context$-$free grammar that produces all palindromes over $.$ Should $lon$ be part of

the grammar? Explain your answer.

$[5/39]$ Using the above grammar, parse the following input: "abba".