1
$\begingroup$

Can somebody explain or possible solve the following question regarding the pumping lemma?

I have a book from Sipser that I took this from and I honestly can't really get a good grasp of the pumping lemma technique, much less solve anything using it.

Use the pumping lemma to show that the language $L=\{\,a^ib^jc^k\mid i<j,j<k\,\}$ is not regular.

From what I understand here, it needs to be used to prove that a language where there is less a's than b and less b's than c's is not regular.

I appreciate it.

$\endgroup$
1
  • $\begingroup$ I'd appreciate if you'd type that short statement instead of linking an image. $\endgroup$ Jan 30, 2014 at 22:11

2 Answers 2

2
$\begingroup$

HINT: let $p$ be the pumping length: consider the word: $w = a^pb^{p+1}c^{p+2}$. Let $w = xyz$ such that $|y| \geq 1$. What does $y$ look like? And what can you do with this knowledge to pump this word $w$ into a word not in $L$?

$\endgroup$
1
$\begingroup$

Assume $L$ is regular with pumpinhg length $n$. Then $a^nb^{n+1}c^{n+2}\in L$ can be writteen as $uvw$ so that $v$ is nonempty and all $uv^iw$ are in $L$. If $v=a^r$ then $uv^2w=a^{n+r}b^{n+1}c^{n+2}\notin L$. If $v=b^r$ then $uv^2w=a^{n}b^{n+1+r}c^{n+2}\notin L$. If $v=c^r$ then $uw=a^nb^{n+1}c^{n+2-r}\notin L$. Therefore $v$ contains two different letters. But then $uvvw\notin L$.

$\endgroup$
1
  • $\begingroup$ $v$ can only contain $a$'s since $|uv| \leq n$. $\endgroup$
    – sxd
    Jan 30, 2014 at 22:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .