1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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! $\endgroup$
    – awillia91
    Mar 31 at 12:27
  • $\begingroup$ @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? $\endgroup$
    – mhanxsolo
    Mar 31 at 12:51
  • $\begingroup$ 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$? $\endgroup$
    – awillia91
    Mar 31 at 13:16
  • $\begingroup$ @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! $\endgroup$
    – mhanxsolo
    Mar 31 at 15:04
  • $\begingroup$ 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. $\endgroup$
    – awillia91
    Mar 31 at 15:16
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.