Construct context free grammar which generates following language $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$

Question

(i) $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$

So far I have

$E \to EcE$

$E \to a$

$E \to b$

$E \to c$

But I'm new at this and feel I'm miles away from a finished answer

Answer 1

What you have generates the language $\{aca,acb,acc,bca,bcb,bcc,cca,ccb,ccc\}$. As you can see, it’s far from being what you want: it’s missing most of the words that you do want, and it contains six words that you don’t want.

The trick is to generate the $w$ and $w^R$ parts at the same time. Suppose that you have the productions $E\to aEa$ and $E\to cEc$. Then you can build derivations like this one:

$$E\to aEa\to acEca\to accEcca\to accaEacca$$

Notice that this automatically produces strings of the form $wEw^R$ — every possible string of that form, in fact. You need to add two more productions to this grammar to get one that generates the desired language; can you see what they are?