This is a homework problem. The problem is:
Find a grammar that generates this language:
L = {wcw^R: w ∈ {a,b}+ } over alphabet Σ = {a, b, c}.
I have tried many different transitions, but can't find one that creates this. Here is the most recent one I tried that failed:
S -> Sa
S -> Sb
S^R -> aS^R
S^R -> bS^R
S -> a
S-> b
S^R -> a
S^R -> b
Any help pointing me in the right direction would be much appreciated!
$\endgroup$ 22 Answers
$\begingroup$HINT: Build the string from the centre out: $$S\to aSa\mid bSb\mid\ldots$$
$\endgroup$ 2 $\begingroup$This is the same as Brian's, just a slightly different perspective:
It may help to look at the language in the following way. Instead of looking for a grammar, look at the structure of the language. That may suggest a grammar...
It is the smallest language that satisfies: (i) $aca,bcb \in L$ and (ii) if $s \in L$, then so are $asa, bsb$.
$\endgroup$
