# How to determine the beginning of $uv^iw$ in the pumping lemma for regular languages?

Let $$\sum=\{a,b,c,d\}$$, $$L=\{a^ib^jcd^k \big| i\ge0; k>j>0\}$$. Prove that $$L$$ is not regular using pumping lemma.

We can choose the word $$Z=a^0b^{n}cd^{n+1}=b^{n}cd^{n+1}\in L$$. Let $$uvw$$ be the decomposition of $$Z$$ . Because $$|uv|\le n$$ and $$|v|\ge 1$$, $$v=b^t$$, $$1\le t\le n$$ and $$uv^2w=b^{n+t}cd^{n+1}$$. Because $$t\ge 1$$ then $$n+t\ge n+1$$ so $$uv^2w\notin L$$ in contradiction to the given.

What I don't understand here is why $$uv=b$$. Usually, according to the pumping lemma:

$$\exists n\ge 1, n\in \mathbb N$$, such that for all $$Z\in L$$, $$|Z|\ge n$$ exists a decomposition $$Z=uvw$$ such that $$|uv|\le n$$, $$|v|\ge 1$$, for all $$n\ge 0$$ and $$Z_n=uv^nw$$.

Thus for example for $$\sum=\{a,b\}, Z=a^nb^b\quad$$ $$\exists s,t:s \ge 0, t\ge 1, s+t\le n$$ so $$u=a^s, v=a^t, w=a^{n-s-t}b^n$$.

How does this definition apply to the decomposition of $$b^ncd^{n+1}$$? Shouldn't $$u=b^s, v=c^t, w=b^{n-s-t}c^td^{n+1}$$?

## 1 Answer

As stated in the lemma, $$uv$$ has at most $$n$$ symbols. Further, $$uv$$ is a prefix of the word $$b^ncd^{n+1}$$, because your factorization is $$uvw = b^ncd^{n+1}$$. Because all of the first $$n$$ symbols of $$b^ncd^{n+1}$$ are $$b$$, both $$u$$ and $$v$$ can only contain $$b$$s.

I suppose $$uv=b$$ is a typo (this is not claimed anywhere), and you mean you do not understand why $$uv = b^j$$ for some $$j$$.

The decomposition you propose is of a string $$b^s c^t, b^{n-s-t}c^td^{n+1}$$, which has several $$c$$ and two changes from $$b$$ to $$c$$, if all exponents are non-zero. So the factored word is not $$b^ncd^{n+1}$$.

• I got it, indeed because the first $n$ symbols of $b^ncd^{n+1}$ are $b$'s, therefore the prefix is $b^n$. Then let $t\ge 1, s\ge 0, s+t\le n\implies u=b^s, v=b^t, w=b^{n-s-t}cd^{n+1}\implies Z=b^{n+t(i-1)}cd^{n+1}$. So for $i=2$ we get $b^{n+t}cd^{n+1}$. – Yos Nov 10 '18 at 11:09