Proving a language with $(ab)^n$ is not regular with pumping lemma?

Question

I have been working to understand the pumping lemma better, but I am quite stuck at proving these two languages is not regular:

\begin{align} L_1 &= \{(ab)^n c^m \mid n\ge 1, m\ge 2n \} \\ L_2 &= \{(ab)^n a^k (ba)^n \mid k<3\} \end{align}

For $L_2$ my approach was:

Let us be given a number $p$. Let $z = (ab)^p a^k (ba)^p$, which satisfies $|z| = 2p > p$, and let $z = uvw$ be its decomposition satisfying $|uv| \leq p$ and $|v| > 0$. This means that $v = (ab)^j$ for some $0 \le j \le p$. We choose $i = 2$ for $uv^iw$, which equals $(ab)^{p+j} a^k (ba)^p$. This word has more $ab$ than $ba$, which means that it doesn't belong to the language. Therefore $L_2$ is not regular.

Mainly I am actually confused with the $(ab)^n$, we should decomposed it so that we can pump $v$, but it is necessary to consider different cases of $v$, or is this sufficient?

Answer 1

Let's suppose, for concreteness, that $p = 3$.

You choose the word $z = (ab)^3a^k(ba)^3$. How does this word look like? It is impossible to tell, since we don't know what the value of $k$ is. Let's therefore take $k = 3$, that is, we are looking at the word $z = (ab)^3(ba)^3 = abababbababa$.

Next, we are given a decomposition $abababbababa = uvw$, where $|uv| \leq 3$ and $v \neq \epsilon$. There are six possibilities:

1. $u = \epsilon$, $v = a$, $w = bababbababa$.
2. $u = \epsilon$, $v = ab$, $w = ababbababa$.
3. $u = \epsilon$, $v = aba$, $w = babbababa$.
4. $u = a$, $v = b$, $w = ababbababa$.
5. $u = a$, $v = ba$, $w = babbababa$.
6. $u = ab$, $v = a$, $w = babbababa$.

You need to be able to handle all of them. There are four different cases: $v \in (ab)^*$, $v \in (ba)^*$, $v \in a(ba)^*$, $v \in b(ab)^*$. For each of them, you need to find a value of $i$ so that $uv^iw \notin L_2$. When showing that $uv^iw \notin L_2$, you have to show that there are no $n \geq 0$ and $k < 3$ such that $uv^iw = (ab)^n a^k (ba)^n$.