Finding a grammar for a formal language

Question

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.

Could you please help me to find a solution?

Thanks in advance

Answer 1

• 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).

Answer 2

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.