2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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." 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 cs.stackexchange.com? $\endgroup$
    – J..y B..y
    Jul 17, 2023 at 9:38
  • $\begingroup$ 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. $\endgroup$
    – bb94
    Jul 17, 2023 at 16:43

1 Answer 1

6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.