# Finding a grammar for a formal language

I am looking for a grammar that describes the formal language

$L = \{ xyx^R \;|\; x,y \in \{a,b\}^*\}$

where $\{a,b\}^*$ corresponds to the regular expression [ab]*.

If there would be no y and the language would therefore contain all the words that are palindromes there wouldn't be any problem. I just don't get the "y" included therein.

-
what does the $*$ on the $\{a,b\}^*$ mean? If it means words with letters $\{a,b\}$ then these certainly are not palindromes. – Nate Iverson Jun 6 '12 at 13:15
I modified the question to be more comprehendible – muffel Jun 6 '12 at 13:23
Do you realise that this language is just [ab]*? – Peter Taylor Jun 6 '12 at 13:30

• S -> aSa | bSb | A
• A -> aA | bA | $\varepsilon$

This way $x$ and $x^R$ are simultanously generated with the start symbol $S$ in the middle. After that $S$ changes to $A$ in order to produce some word $y$ between $x$ and $x^R$.

Edit: As was pointed out, the language is just $\{a,b\}^*$, so there is a simpler grammar (see the other answer).

-
Missed Peter's point, that this is $[ab]^*$, or in formal language terms (since this is a theoretical question) $(a+b)^*$. So it has a much simpler grammar, though I doubt that was the intended issue. – David Lewis Jun 6 '12 at 14:16

Peter Taylor is correct: $L=\{a,b\}^*$, since any $w\in\{a,b\}^*$ can be written as $\lambda w\lambda^R$, where $\lambda,w\in\{a,b\}^*$. (I use $\lambda$ for the empty word.) Thus, $L$ is regular and is generated by the grammar with initial symbol $S$ and productions $$S\to aS\mid bS\mid\lambda\;.$$ The problem becomes interesting only if $x$ is required to be non-empty.

-
$x\in \{a,b\}^+$ would do what you want. But in fact, it doesn't really get interesting until the set of $x$'s is infinite. – David Lewis Jun 6 '12 at 14:19
What would make it interesting, I think, is if there were letters that were allowed in $x$ but not in $y$. – Henning Makholm Jun 6 '12 at 14:23