Regularity of a language checker I have to check if this language is regular or not:$$L = \{w(bb)^nw^R:w\in\{a,b\}^* \land n \in \mathbb{N}\}$$
My thoughts are if this language is regular so the RE for this is: $(bb)^*$ where $w$ and $w^R$ are empty strings. But if this language is not regular, the pumping lemma doesn't work on this language since there are $2$ different exponents. What do you guys think? Is this language regular or not?
 A: Suppose that $L$ is regular. Since regular languages are closed under Boolean operations, the language
$$
  K = L \cap (ba)^*(ab)^* = \{(ba)^m (ab)^m \mid m \geqslant 0\}
$$
should also be regular. Let $f: \{a,b\}^* \to \{a,b\}^*$ be the monoid morphism defined by $f(a) = ba$ and $f(b) = ab$. Since regular languages are closed under inverses of morphisms, the language
$$
R = f^{-1}(K) = \{a^mb^m \mid m \geqslant 0\}
$$
should also be regular. But I guess you already know that this language is not regular. Thus $L$ is not regular.
A: The pumping lemma in its most common formulation only looks at a prefix of the language's words for a punping site, because there is a length restriction on the first two factors. So for words from your language that have $w$ long enough the $(bb)^n$ part does not really matter for pumping lemma considerations.
So let $k$ be the pumping constant for the language and choose $w=a^k$ and $n=1$ resulting in the word $a^k bb a^k$. Any punping must take place in the prefix consisting of only $a$, which results in an exponent distinct from $k$. The resulting words cannot be in the language, because the final block of $a^k$ cannot be the reverse of the word's prefix up to the first $b$ any more.
