Find a grammar that generates this palindrome language

8.6k Views Asked by At

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!

2

There are 2 best solutions below

2
On BEST ANSWER

HINT: Build the string from the centre out: $$S\to aSa\mid bSb\mid\ldots$$

0
On

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