Prove that $F = \{\,a^i b^j\mid i = kj \text{ for some positive integer }k\ \}$ is not context free

3.6k Views Asked by At

This question is borrowed from sipser 2nd ed.

Show that $F = \{\,a^i b^j\mid i = kj \text{ for some positive integer }k\ \}$ is not context free.

I tried it but did not get any clue about the scenario ; which shall oppose it being context free.

Let pumping length is $p$ and suppose we take string $a^{2p} b^p$ for pumping lemma test.

If we take $a^p$ as pumping portion then it'll always be in the language.

$a^i b^j$ | $i = kj$

Please provide me the scenario which shall work out.

Help appreciated :)

1

There are 1 best solutions below

5
On

Hint: Try to pump $a^{p+1}b^{p+1}$