Pumping Lemma Help

Question

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.

I'd appreciate if you'd type that short statement instead of linking an image. — Hagen von Eitzen, Jan 30 '14 at 22:11

score 2 · Accepted Answer · answered Jan 30 '14 at 22:18

2

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

answered Jan 30 '14 at 22:18

sxd

3,504

score 1 · Answer 2 · answered Jan 30 '14 at 22:19

1

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

answered Jan 30 '14 at 22:19

Hagen von Eitzen

374,180

$v$ can only contain $a$'s since $|uv| \leq n$. – sxd Jan 30 '14 at 22:32

Pumping Lemma Help

2 Answers2