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}$?


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

  • $\begingroup$ 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}$. $\endgroup$ – Yos Nov 10 '18 at 11:09

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.