1
$\begingroup$

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

  • 3
    Do you realise that this language is just `[ab]*`?2012-06-06

2 Answers 2

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

  • 0
    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.2012-06-06
5

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.

  • 0
    What would make it interesting, I think, is if there were letters that were allowed in $x$ but not in $y$.2012-06-06