So i need to prove that the language $L=${${a^ib^j: gcd(i,j)=1}$} is not regular.

For which i chose the string $w=a^{m!}b^p$ where $p>m!$ and is a prime number. clearly $m!$ and p are co-prime so $w$ is in $L$.
Let $w=xyz$ such that $|xy|<=m$ and $|y|>=1$. now the only choice for $y$ in this string is $a^k :k<=m$.
Now pumping it $i$ times we get the string $a^{m!+(i-1)k}b^p$. Choosing $i=1+\frac{(p-1)m!}{k}$. now $i$ is a natural number as $k<=m$ so we get the string $a^{m!p}b^p$ which is not in $L$.
Hence pumping lemma is not satisfied so $L$ is not regular.
Is my reasoning correct? Thanks in advance.

  • $\begingroup$ Seems fine for me :) $\endgroup$ – tarit goswami Sep 28 '18 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.