Question about Notation in a Regular Language

140 Views Asked by At

I am a little confused about the following notation: $L' = \{xy|x\in L \ , y\in L^R\}$. I think this expression is not equivalent with palindrome but I am not entirely sure. For example, I think the following is true: if $L=a^*b$, then $xy = a^5bba^3$is in L. Sorry if this a trivial question but I want to make sure I didn't misunderstand any thing.

Thanks ahead!

1

There are 1 best solutions below

2
On BEST ANSWER

An element of $L'$ could potentially be a palindrome, but that does not rule out the possibility that $L'$ is regular. Some elements of the language $(\mathtt{a}+\mathtt{b})^\ast$ are palindromes—in fact it contains all possible palindromes—but the language is still regular.

A theorem says that if language $X$ is regular, than $X^R$, containing all the words of $X$ written backwards, is also regular. (The proof is essentially, run the FA for $X$, but backwards.) And you know that the concatenation of any two regular languages is regular, so if $X$ is regular, so is the language $XX^R$ consisting of all strings formed by taking an element of $X$ and concatenating it with an element of $X^R$.

$XX^R$ does contain many palindromes, just as $(\mathtt{a}+\mathtt{b})^\ast$ does, but it also contains many non-palindromes, so it is not the same as $\{xx^R \mid x\in X\}$, which in general is not regular.

Your $xy$ example is correct: if $L=\mathtt{a}^\ast\mathtt{b}$ then you can choose $x=\mathtt{a}^5\mathtt{b} \in L$ and $y = \mathtt{ba}^3\in L^R$ and then $xy = \mathtt{a}^5\mathtt{b}\mathtt{ba}^3\in LL^R$ even though it is not a palindrome.