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.
Is the language of strings with an integer ratio of the number of a's to the number of b's context-free?
formal languages;context free
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. 