how to prove that the following is not a regular language?

Question

the language we want to disprove is :

$$ L = \{ 0^i1^j| gcd(i,j)=1 \} $$

my attempt :

i used the pumping lemma this way:

consider the set of strings of the form $0^p1^q$ such that $n <=p$ and $p\in primes$ and $q\in primes$

note $n$ is the number that lemma states it exists .

now using pumping lemma we get :

$xy = 0^m$ where $m<= p$

$ y = 0^k $ so $x= 0^{m-k}$ so $z = 0^{p-m}1^q$

now lemma says all string of the form $xy^iz\in language$

now the sum of all $0$'s for all theses strings is : $p+(i-1)k$

now we choose from our set the string which has $q = k+1$

and we set $i = p+1$

now we have $gcd(p(k+1),k+1) = k+1$

so we have disproved the statement.

is the proof right ? is choosing a set of counter examples and then choosing one among them correct?

Answer 1

For the record, there is a very simple proof using the Myhill–Nerode criterion. Let $p_i$ be an enumeration of all primes. Since $0^{p_i} 1^{p_i} \notin L$ while $0^{p_j} 1^{p_i} \in L$ (for $j \neq i$), we see that the words $0^{p_i}$ are pairwise inequivalent with respect to $L$, and so $L$ is not regular.

If you really need to use the pumping lemma, let $n$ be the pumping length, and pick a prime $p \geq n+2$. Consider the word $0^p 1^{(p-1)!} \in L$. The pumping lemma states that you can write $0^p 1^{(p-1)!} = xyz$, with $|xy| \leq n$ and $|y| \geq 1$, such that $xy^i z \in L$ for all $i \geq 0$. In our case, we must have $y = 0^k$, where $1 \leq k \leq n \leq p-2$, and so $xz = 0^{p-k} 1^{(p-1)!}$. Since $k \leq p-2$, we have $2 \leq p-k \leq p-1$, and so $\mathrm{gcd}(p-k,(p-1)!) = p-k > 1$, implying $xz \notin L$. This contradiction shows that $L$ is not regular.

Answer 2

The decomposition into $xyz$ is dependent on what input string $0^p1^q$ you choose, therefore, $k$ is a function of $p$ and $q$, so you cannot just set $q = k+1$ afterwards.

I would choose $0^p1^{(p-1)!}$ for some $p$ prime at least two greater than the pumping length, since then $xy^0z = xz = 0^k1^{(p-1)!}$ for $k<p$. This is possibly not the most slick proof.