1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does the exercise explicitly ask you to do it using the Pumping Lemma? Because I personally think that it is almost always more convenient to use the characterization of regular languages using Myhill-Nerode equivalence classes (if you are familiar with those). $\endgroup$ – PhoemueX Nov 2 '15 at 17:36
  • $\begingroup$ It explicitly asks for the pumping lemma. It is one of the "!!" challenge problems in $\textit{An Introduction to Automata Theory, Languages, and Computation}$ and we haven't talked about Myhill-Nerode equivalences classes there, nor have I worked with them before $\endgroup$ – tzamboiv Nov 3 '15 at 2:53
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Could you elaborate a little more on the last step, about how to show that $kr-1$ is a multiple of $p$? $\endgroup$ – tzamboiv Nov 2 '15 at 8:25
  • $\begingroup$ @ejz: Let me ask first whether you’ve had any elementary number theory or group theory. $\endgroup$ – Brian M. Scott Nov 2 '15 at 8:26
  • $\begingroup$ I have not had experience with those $\endgroup$ – tzamboiv Nov 2 '15 at 8:30
  • $\begingroup$ @ejz: Okay; that makes it a little harder. I’ll add a bit. $\endgroup$ – Brian M. Scott Nov 2 '15 at 8:32
  • $\begingroup$ @ejz: Let me ask one more question: are you familiar with the Euclidean algorithm for finding the greatest common divisor of two integers? $\endgroup$ – Brian M. Scott Nov 2 '15 at 8:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.