# Is the language of strings with an integer ratio of the number of a's to the number of b's context-free?

Consider the language $L \subseteq \{a,b,c\}^*$, where $w \in L$ if and only if the ratio of the number of $a$'s in $w$ to the number of $b$'s in $w$ is an integer. I've been unable to find a counterexample string in $L$ which I can use to disprove (via a contradiction proof using the pumping lemma for CFLs) that $L$ is a CFL. This suggests that $L$ may be recognized by a nondeterministic PDA.

Now, if $\#_a(w) = i\cdot \#_b(w)$ for some $i \geq 0$, then I can perfectly match every single $b$ with $i$ $a's$. The problem is that since $i$ can be any nonnegative integer, there are strings in $L$ for which I'd need to match every one $b$ with one $a$, strings for which I'd need to match every two $a$'s with one $b$, and so on. I don't see how a nondeterministic PDA has the capacity to cover all such (i.e., infinitely many) matchings.

The language is not a CFL. The string $w$ that is the counter example to the pumping lemma is $a^{(N+1)^2}b^{(N+1)}$ where $N\geq 1$ is the pumping length. The idea is to take the number of $a$'s comparably larger by an order of $N$ to the number of $b$'s. Then if you pump you get strings with $\#_a={(N+1)^2+ik_1}$ and $\#_b ={N+1+ik_2}$ for $i\geq -1$. You would be able to prove that his string does not belong to $L$ for some $i$ and for any $k_1+k_2\leq N$.

Or if we take some crazy long string like $w = a^{(2N)!}b^{N+1}$, noting that the pumped string will have $\#_a={(2N)!+ik_1}$ and $\#_b={N+1+ik_2}$ for $i\geq -1$. If $k_1 = 0$ then we can take $i > \frac{(2N)! - N -1}{k_2}$. If $k_1 > 0$ then for $i=1$, $\frac{(2N)!+k_1}{N+1+k_2}$ is a proper fraction, since $0\leq k_2 \leq N-1$, $1 \leq k_1 \leq N$ and therefore $N+1 \leq N+1+k_2 \leq 2N$ which implies $0<\frac{k_1}{N+1+k_2}<1$ is a fraction.

• How do we know that $\frac{(N+1)^2 + k_1}{N+1 + k_2}$ is not an integer? Mar 23, 2016 at 2:02
• Sorry for $i=1$ the fraction is not always an integer. You will need to take a large value of $i$. Mar 23, 2016 at 2:30
• Just a nit to pick: when pumping, the number of $a$ and $b$ are as you state, but you can end up with a mixture of $a$ and $b$, not clean $a$s then $b$s. Mar 23, 2016 at 16:11
• @DavidSmith, that is precisely the point. That fraction can't be an integer for all $i$. Mar 23, 2016 at 16:13
• @vonbrand, I will modify the answer to reflect mixed strings. Mar 23, 2016 at 17:21

You could use Parikh's theorem. Suppose that your language is context-free. Then its commutative image $$c(L) = \{(|u|_a, |u|_b, |u|_c) \mid u \in L \} = \{ (rn, n, m) \mid r >0, n \geqslant 0, m \geqslant 0\}$$ would be a semilinear set of $\mathbb{N}^3$. By projection, the set $R = \{ (rn, n) \mid r >0, n \geqslant 0\}$ would be a semilinear set of $\mathbb{N}^2$. Observe that $$\{ (rn, n) \mid r >1, n > 1\} = R \setminus ( S \cup T)$$ with $S = \{ (n, n) \mid n \geqslant 0\}$ and $T = \{ (r, 1) \mid r >0\})$. Since $S$ and $T$ are semilinear and since semilinear sets are closed under Boolean operations, the set $\{ (rn, n) \mid r >1, n > 1\}$ would be semilinear. Thus its projection $\{ rn \mid r >1, n > 1\}$ would be a semilinear set of $\mathbb{N}$, and so would be its complement $\{0,1\} \cup \{ p \mid p \text{ is prime }\}$, which is certainly not the case. Thus $L$ is not context-free.