Show that the language $\{0^$a$1^$b$|$ a $=$ kb for some k in N$\}$ is not context$-$free. This language

contains strings such as $0011($k $=1),00001($k $=4),$ and $001($k $=2),$ but does not contain $00011$

$($because a $=1\mathrm{.}5$ b and $1\mathrm{.}5$ in $/$ N$).$ A string of the form $0$a$1$

b belongs to this language, unless a

b

in $/$ N$.$

Choose your string s of size $|$s$|>=$ p carefully, and use the pumping lemma to reach a contradiction. Even if you cannot identify an appropriate string s$,$ you can get partial credit if you formally

explain what exactly you would need to show to reach a contradiction, paying close attention to

the quantifiers and the case analysis.

$($Hint: if a is a multiple of b$,$ then a $+$ c is a multiple of b if and only if c is a multiple of b$)$