Question.
Determine if the languages are regular:
$L_{1}=\{(ab)^{k}a(ba)^{k}\,|\,k\geq0\}$
$L_{2}=\{(ab)^{k}b(ba)^{k}\,|\,k\geq0\}$
I think both are not regular, I used the Pumping Lemma to prove, But the proof is exactly the same and it's a bit suspicious. Is it true that both are not regular?
$L_1$ is actually regular. You can see this by regrouping terms as follows:
$L_{1}=\{a(ba)^{k}(ba)^{k}\,|\,k\geq0\}=\{a(ba)^{2k}\,|\,k\geq0\}=\{a(baba)^{*}\}$
$L_2$ appears to be non-regular, however. The key observation is that the middle '$b$' in the expression appears to divide the strings in such a way as to force the left and right portions to have to balance (like parentheses). There is probably a 'homomorphism'-based proof starting with the language $\{(^{k}b)^{k}\,|\,k\geq0\}$, mapping '$($' to '$ab$' and '$)$' to '$ba$'. But I don't have time to formally verify this.