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

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?

• I think you have the right general idea here, but I suggest thinking about a few things. First, what is the length of z? Are you sure you calculated it correctly? Second, are you sure about your assertion that $v=(ab)^j$? I think you have a few more cases to consider, but you’re definitely on the right track! – awillia91 Mar 31 at 12:27
• @awillia91 firstly thanks for the reply! I think the length may be wrong, but the idea was the length of this word is larger than the number of states p and with the condition |uv|<=p, v is probably a composition of a's and b's. Do you have an idea which cases it could possibly be? – mhanxsolo Mar 31 at 12:51
• Right, you definitely have the right idea! And the specific length is not that important, as long as it’s greater than the pumping length, but since you wrote it I suggest either giving the exact length or asserting that it’s greater than the pumping length by an argument like $\lvert z \rvert > \lvert (ab)^p \rvert = 2p >p$. Now v could be one character (e.g, $v=b$) or a sequence of characters, and different values of $k$ might lead to different approaches as well. It’s relatively easy to rule out v being one letter. But in your example what if $k=1$? Is it obvious that $z$ is not in $L_2$? – awillia91 Mar 31 at 13:16
• @awillia91 you are right! So I need to consider v can be either a or b, then it is important that the length of v, if it is odd than it definitely contradict the language form when you pump v. In case |v| is even, when pumping for example i = 2, i is at least p+1, which contradict the language. thanks I did not consider a^k, which needs to be considered as well! – mhanxsolo Mar 31 at 15:04
• I think you will also want to pick a specific value for $k$,I suggest $0$ or $2$. I think $k=1$ will give you some problems. – awillia91 Mar 31 at 15:16

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$$.