<p>You can solve this using <a href="https://en.wikipedia.org/wiki/Parikh%27s_theorem" rel="noreferrer">Parikh's theorem</a>. We want to prove that the set <span class="math-container">$A = \{(a, b)\in\mathbb{N_{&gt;0}}^2 | a-b\sqrt2 \geq 0\} = \{(a,b)\in\mathbb{N_{&gt;0}}^2 | \frac ab\geq\sqrt2\}$</span> isn't semilinear (even if you allow <span class="math-container">$n$</span> or <span class="math-container">$m$</span> to be 0 this is enough due to intersection with a regular language). We'll show that for any linear set <span class="math-container">$L$</span>, <span class="math-container">$\inf \{\frac ab | a, b \in L\}$</span> is rational, and thus <span class="math-container">$A$</span> can't be a union of a finite number of linear sets.</p>
<p>Suppose that <span class="math-container">$L = u_0 + \mathbb{N} u_1 + \dots + \mathbb{N} u_n$</span>. Let's define <span class="math-container">$f((x, y)) = \frac x y$</span>. We'll prove that <span class="math-container">$f(u_0 + t_1 u_1 + t_2u_2 \dots + t_nu_n) \geq \min_{i} f(u_i)$</span>. Using induction on <span class="math-container">$n$</span>, we can see it's enough to prove that <span class="math-container">$f(a u + v) \geq \min\{f(u), f(v)\}$</span> when <span class="math-container">$a&gt;0$</span>, but this is trivial from the <a href="https://en.wikipedia.org/wiki/Mediant_(mathematics)" rel="noreferrer">mediant inequality</a>. We've show that <span class="math-container">$\{\frac ab|(a,b)\in L\}$</span> is bounded by <span class="math-container">$\min_i f(u_i)$</span>, now we'll show it can get as close as we want to it. Our first case is that <span class="math-container">$\min_i f(u_i) = f(u_0)$</span>. In that case, since <span class="math-container">$u_0 \in L$</span>, we can just take it and we achieve the infimum. Otherwise, suppose that <span class="math-container">$\min_i f(u_i) = u_i$</span>. As <span class="math-container">$n$</span> approaches <span class="math-container">$\infty$</span>, <span class="math-container">$f(u_0 + n u_i)$</span> approaches <span class="math-container">$u_i$</span> - <span class="math-container">$$\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)$$</span>
We've shown that <span class="math-container">$\inf \{\frac ab | a, b \in L\} = \min_i {f(u_i)}$</span>, 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 <span class="math-container">$A$</span>, since its corresponding infimum is <span class="math-container">$\sqrt2$</span> which is irrational.</p>
<p>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 (<span class="math-container">$b$</span> 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 <span class="math-container">$x+y$</span> approaches infinity).</p>
<p>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 <span class="math-container">$b$</span>, 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).</p>

CC BY-SA 4.0
2023-07-18T04:55:32.720Z
2023-07-18T04:55:32.720Z
Command Master
<p>Is the language <span class="math-container">$a^m b^n$</span> where <span class="math-container">$m - n \sqrt{2} \ge 0$</span> 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.</p>
<p>More generally, given <span class="math-container">$\Sigma = \{a_1, a_2, \ldots, a_k\}$</span> and  <span class="math-container">$b, w_1, w_2, \ldots w_k \in \mathbb{R}$</span>, define <span class="math-container">$L = \{s \in \Sigma^* | \sum_{i = 1}^k w_i N(s, a_i) \ge b \} $</span>, where <span class="math-container">$N(s, c)$</span> denotes the number of times the character <span class="math-container">$c$</span> occurs in <span class="math-container">$s$</span>. Then if <span class="math-container">$L$</span> is context-free, can <span class="math-container">$w_1, w_2, \ldots, w_k$</span> always be expressed as integers? (Assuming that <span class="math-container">$w_1, w_2, \ldots w_k$</span> contains both positive and negative weights; otherwise, <span class="math-container">$L$</span> would be regular.)</p>

CC BY-SA 4.0
2023-07-17T09:38:57.823Z
This question looks like an undergraduate programming exercise, which would not be adequate for cstheory SE ("a question and answer site for professional researchers in theoretical computer science and related fields." https://cstheory.stackexchange.com/tour). If it is not, sharing some information about where it comes from would motivate your peers to work on it. If it is, maybe you should ask on a more adequate stack exchange channel, like https://cs.stackexchange.com/?
J.y B.y
CC BY-SA 4.0
2023-07-17T16:43:55.017Z
My initial motivation was in imagining a spoken language in which morphemes alternated depending on such a score for the stem. (Such a language would almost certainly be a conlang.) For example, imagine that this language had a suffix that manifested as *-ta* when the stem has at least as many voiced consonants as voiceless ones, and *-da* when it has more voiced consonants than voiceless. If both positive and negative weights are present, this criterion already fails to be a regular language.
bb94
<automata-theory><linear-equations>
Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?
bb94
# Is $a^m b^n$ where $m - n \sqrt{2} \ge 0$ context-free?

(Asked by: username_0 on 2023-07-17)

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

**Tags:** automata-theory, linear-equations
> **Comments:**
> **username_1**: This question looks like an undergraduate programming exercise, which would not be adequate for cstheory SE ("a question and answer site for professional researchers in theoretical computer science and related fields." https://cstheory.stackexchange.com/tour). If it is not, sharing some information about where it comes from would motivate your peers to work on it. If it is, maybe you should ask on a more adequate stack exchange channel, like https://cs.stackexchange.com/?  
> **username_0**: My initial motivation was in imagining a spoken language in which morphemes alternated depending on such a score for the stem. (Such a language would almost certainly be a conlang.) For example, imagine that this language had a suffix that manifested as *-ta* when the stem has at least as many voiced consonants as voiceless ones, and *-da* when it has more voiced consonants than voiceless. If both positive and negative weights are present, this criterion already fails to be a regular language.  

---

## 1 answers

### Answer by username_2 on 2023-07-18. Score: 6 | Accepted answer

You can solve this using [Parikh's theorem](https://en.wikipedia.org/wiki/Parikh%27s_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](https://en.wikipedia.org/wiki/Mediant_(mathematics)). 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).


---

