CFG with reverse strings

5.9k Views Asked by At

I've been trying to figure this out for a while, and I'm at a total loss:

Write a context-free grammar that generates the language $\{x y\ |\ x$ is a string over $\{a,b,c\},\ y$ is a reverse of $x\}$.

1

There are 1 best solutions below

0
On

How about this one:

$$S\rightarrow \lambda,\quad S\rightarrow aSa,\quad S\rightarrow bSb,\quad S\rightarrow cSc$$