8
$\begingroup$

Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?

I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers are co-prime or not.

I tried using the pumping lemma to no avail.

Any help would be gladly appreciated.

Edit:

Here is one of my failed attempts with the pumping lemma:

Let $N$ be a constant. Take a prime $p$ such that $p > N!$ and then take the word $z = 0^p 1^{p+N!} \in L$. Let $ z = uvwxy $ be a decomposition of $z$ satisfying the conditions in the pumping lemma.

If $ vx $ contains only zeros then $ |vx| = k $ is an integer between $1$ and $N$. Define $m$ as $m = N!/k$. For $i = m+1$ the word $ uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L $

However, I've failed to find such an integer $i$ for the other decomposition cases.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! Let me direct you towards our reference questions which might cover your problem. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. I think Parikh's theorem might work out for you. $\endgroup$ – Raphael♦ Apr 11 '13 at 22:36
  • 2
    $\begingroup$ Parikh should work, but also standard pumping/Ogden, right? $\endgroup$ – Ran G. Apr 12 '13 at 2:48
  • $\begingroup$ It's actually a quiz question. Since we haven't learned Parikh's theorem there is probably a way to show that it's not context free with the pumping lemma or with closure properties. $\endgroup$ – Robert777 Apr 12 '13 at 10:02
  • $\begingroup$ @Raphael, in this case Parikh's theorem doesn't really add anything beyond straight pumping lemma (i.e., from $0^n 1^m$ can get all $0^{n + k a} 1^{m + k b}$ for some $a$, $b$ not both zero and $k \ge -1$). But I don't see any way to force $\gcd(n + k a, m + k b) \ne 1$. $\endgroup$ – vonbrand Apr 12 '13 at 12:26
  • $\begingroup$ @vonbrand We may work on $\overline{L} \cap \mathcal{L}(0^*1^*)$ instead; see here. $\endgroup$ – Raphael♦ Apr 12 '13 at 12:35
4
$\begingroup$

Ridiculous that I didn't see this earlier...

The proof that the language (call it $\mathcal{L}$) isn't context free is by contradiction. Assume $\mathcal{L}$ is context free, by the pumping lemma for CFGs there is a constant $N$ such that each string $\sigma \in \mathcal{L}$ such that $\lvert \sigma \rvert \ge N$ it can be written $\sigma = u v x y z$ with $v y \ne \epsilon$ such that for all $k \ge 0$ the string $u v^k x y^k z \in \mathcal{L}$. Take $m, n$ different primes (such that $\gcd(m, n) = 1$) and $m, n > 2N$, and take $\sigma = 0^m 1^n$. The pumped string will be $0^{m + k a} 1^{n + k b}$ for some constants $a$, $b$, not both zero, and such that $a < m$ and $b < n$ (we have $a, b \le N < m / 2, n / 2$ by the way $m$, $n$ were selected). The case of one of them zero was covered by OP, so consider $a, b \ne 0$. Now:

$$ \begin{align*} m + k a &\equiv 0 \pmod{n} \\ n + k b &\equiv 0 \pmod{m} \end{align*} $$

This has a unique solution $k^*$ modulo $m n$ by the chinese remainder theorem (we have $a < n$, and as $n$ is prime, $\gcd(a, n) = 1$; similarly $b$ and $m$), and thus we can write: $$ \begin{align*} m + k^* a &\equiv 0 \pmod{mn} \\ n + k^* b &\equiv 0 \pmod{mn} \end{align*} $$ i.e., $m n \mid \gcd(m + k^* a, n + k^* b)$. Contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your reply. I liked the way you approached this. However, I don't understand how did you use the chinese remainder theorem if this can only be applied on a system of linear congruences of the form: $$ \begin{align*} x &\equiv b1 \pmod{m1} \\ x &\equiv b2 \pmod{m2} \end{align*} $$ $\endgroup$ – Robert777 Apr 12 '13 at 14:49
  • $\begingroup$ @Robert777, just write $k a \equiv -m \pmod{n}$ and so on. $\endgroup$ – vonbrand Apr 12 '13 at 14:56
  • 1
    $\begingroup$ but you get a congruence of the form: $$ \begin{align*} a x &\equiv b \pmod{m} \\ \end{align*} $$ and it's not the same. For example if $ gcd(a,m) \not | b $ then the congruence has no solutions. $\endgroup$ – Robert777 Apr 12 '13 at 15:01
  • 1
    $\begingroup$ @Robert777, you are absolutely right. Changed to select $m$, $n$ prime. Thanks! $\endgroup$ – vonbrand Apr 12 '13 at 20:06
  • $\begingroup$ Okay, after we've used the chinese remainder theorem, why can we write these congruences: $$ \begin{align*} m + k^* a &\equiv 0 \pmod{mn} \\ n + k^* b &\equiv 0 \pmod{mn} \end{align*} $$ $\endgroup$ – Robert777 Apr 12 '13 at 21:11

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.