Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted
  • 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).

share|cite|improve this 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.

share|cite|improve this answer
$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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.