Context-free grammar and Reversal

I'm designing a context-free grammar to generate this language:开发者_开发问答

{ w in {a,b}* | w is of the form uvu^R, where u and v are any strings in {a,b}* }

I would define the first two strings as:

U -> aU | bU | _
V -> aV | bV | _

And then combine those:

S -> UV

But how do I express the reversal as context-free grammar?

You need to make use of the context-free-ness of the grammar (what you're presenting so far is just a regular grammar):

U-> aUa | bUb | a | b | _

Will match things like "ababa" and "aabaa", but not "aabba".

I'll leave it to you to alter this to your needs - but keep in mind that your specified language has the possibility of u being the empty string, hence it generates all strings in {a,b}*.