[Math] Pumping Lemma for $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$

computer scienceregular-language

Let $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$ I want to prove that this is not a regular language, but I am having trouble finding a string I can pump resulting in the string not being in the language. Ideally, rather than a full solution, I'd like suggestions for a string that I could use in this proof. I've played with the idea of setting $j = 2$ and $i = 2n+1$, but I don't think that would work.

Best Answer

Let $p$ be a prime number greater than the pumping length, and try $0^{p-1}1^p$. Show that when you pump up, you get something of the form $0^{p-1+kr}1^p$ for some $r$ such that $1\le r<p$, and show that there is a $k\ge 1$ such that $kr-1$ is a multiple of $p$, i.e., such that $kr\equiv 1\pmod p$.

Related Question