Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?

Question

Is the language $a^m b^n$ where $m - n \sqrt{2} \ge 0$ a context-free language? I’m suspecting that it’s not, but I haven’t been able to prove so using the pumping lemma for context-free languages.

More generally, given $\Sigma = \{a_1, a_2, \ldots, a_k\}$ and $b, w_1, w_2, \ldots w_k \in \mathbb{R}$, define $L = \{s \in \Sigma^* | \sum_{i = 1}^k w_i N(s, a_i) \ge b \} $, where $N(s, c)$ denotes the number of times the character $c$ occurs in $s$. Then if $L$ is context-free, can $w_1, w_2, \ldots, w_k$ always be expressed as integers? (Assuming that $w_1, w_2, \ldots w_k$ contains both positive and negative weights; otherwise, $L$ would be regular.)

Answer 1

You can solve this using Parikh's theorem. We want to prove that the set $A = \{(a, b)\in\mathbb{N_{>0}}^2 | a-b\sqrt2 \geq 0\} = \{(a,b)\in\mathbb{N_{>0}}^2 | \frac ab\geq\sqrt2\}$ isn't semilinear (even if you allow $n$ or $m$ to be 0 this is enough due to intersection with a regular language). We'll show that for any linear set $L$, $\inf \{\frac ab | a, b \in L\}$ is rational, and thus $A$ can't be a union of a finite number of linear sets.

Suppose that $L = u_0 + \mathbb{N} u_1 + \dots + \mathbb{N} u_n$. Let's define $f((x, y)) = \frac x y$. We'll prove that $f(u_0 + t_1 u_1 + t_2u_2 \dots + t_nu_n) \geq \min_{i} f(u_i)$. Using induction on $n$, we can see it's enough to prove that $f(a u + v) \geq \min\{f(u), f(v)\}$ when $a>0$, but this is trivial from the mediant inequality. We've show that $\{\frac ab|(a,b)\in L\}$ is bounded by $\min_i f(u_i)$, now we'll show it can get as close as we want to it. Our first case is that $\min_i f(u_i) = f(u_0)$. In that case, since $u_0 \in L$, we can just take it and we achieve the infimum. Otherwise, suppose that $\min_i f(u_i) = u_i$. As $n$ approaches $\infty$, $f(u_0 + n u_i)$ approaches $u_i$ - $$\lim_{n\to\infty}{f(u_0 + nu_i)} = \lim_{n\to\infty}{\frac{u_{00} + nu_{i0}}{u_{01} + nu_{i1}}} = \lim_{n\to\infty}\frac{\frac{u_{00}}n + u_{i0}}{\frac{u_{01}}n + u_{i1}} = f(u_i)$$ We've shown that $\inf \{\frac ab | a, b \in L\} = \min_i {f(u_i)}$, which is a rational number, and since that infimum of a finite union is the minimum of their infima it must be rational, and thus the union can't be $A$, since its corresponding infimum is $\sqrt2$ which is irrational.

For your generalized case, by intersecting with a regular language, we can show that it isn't possible if there are two weights with an irrational ratio ($b$ is annoying, but I believe it doesn't matter for the ratios as the length approaches infinity. You might need a more intricate argument, looking at the limit inferior as $x+y$ approaches infinity).

If all pairs of weights have a rational ratio, we can convert them all to integers by multiplying with some constant, take the ceiling of $b$, and once they are all integers it's easy to solve using a PDA (maintain the sum as the length of the stack, while keeping track of the sign in the state).