10
$\begingroup$

I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ where $\gamma$ is some irrational number. How would I prove that $L$ is not a context-free language?

In the case when $\gamma$ is rational, it's pretty easy to construct a grammar that accepts the language. But because $\gamma$ is irrational, I don't really know what to do. It doesn't look like any of the pumping lemmas would work here. Maybe Parikh's theorem would work here, since it would intuitively seem like this language doesn't have an accompanying semilinear Parikh image.

This exercise is from "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit, Exercise 25 of Chapter 4.

I would really appreciate any help, or nudges in the right direction. Thank you!

$\endgroup$
  • $\begingroup$ Have you tried applying Parikh’s theorem? $\endgroup$ – Yuval Filmus Mar 20 at 15:44
  • $\begingroup$ Why not show that it’s not semilinear directly? Use the definition. $\endgroup$ – Yuval Filmus Mar 20 at 15:53
  • 4
    $\begingroup$ Just in time for my homework! Thanks. CS 462/662 Formal Languages and Parsing Winter 2019, Problem Set 9, exercise 3. Due Friday, March 22 2019. $\endgroup$ – Hendrik Jan Mar 20 at 19:36
  • $\begingroup$ @HendrikJan I'm selfstudying from the textbook "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit. It is Exercise 25 of Chapter 4 fyi. Would it be possible to hide this post until the assignment is due? $\endgroup$ – user101859 Mar 20 at 22:42
  • $\begingroup$ I appreciate what you were trying to do and your good intentions, but please don't destroy the question by editing it to hide the question (even for a few days). Thank you. P.S. Thank you for crediting the source of the problem! $\endgroup$ – D.W. Mar 20 at 23:14
7
$\begingroup$

According to Parikh's theorem, if $L$ were context-free then the set $M = \{(a,b) : a \leq \gamma b \}$ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_\ell$, for some $u_i = (a_i,b_i)$.

Obviously $u_0 \in M$, and moreover $u_i \in M$ for each $i > 0$, since otherwise $u_0 + N u_i \notin M$ for large enough $N$. Therefore $g(S) := \max(a_0/b_0,\ldots,a_\ell/b_\ell) < \gamma$ (since $g(S)$ is rational). This means that every $(a,b) \in S$ satisfies $a/b \leq g(S)$.

Now suppose that $M$ is the union of $S^{(1)},\ldots,S^{(m)}$, and define $g = \max(g(S^{(1)}),\ldots,g(S^{(m)})) < \gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b \leq g < \gamma$, and we obtain a contradiction, since $\sup \{ a/b : (a,b) \in M \} = \gamma$.


When $\gamma$ is rational, the proof fails, and indeed $M$ is semilinear: $$ \{ (a,b) : a \leq \tfrac{s}{t} b \} = \bigcup_{a=0}^{s-1} (a,\lceil \tfrac{t}{s} a \rceil) + \mathbb{N} (s,t) + \mathbb{N} (0,1). $$ Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a \leq \tfrac{s}{t} b$ (since $s = \tfrac{s}{t} t$). Conversely, suppose that $a \leq \frac{s}{t} b$. While $a \geq s$ and $b \geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a < s$ (since $b < t$ implies $a \leq \frac{s}{t}b < s$). Since $a \leq \frac{s}{t} b$, necessarily $b \geq \lceil \tfrac{t}{s} a \rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,\lceil \tfrac{t}{s} a \rceil)$.

$\endgroup$
  • $\begingroup$ Nice answer. Just a clarification, the logic behind "every $(a,b) \in S$ satisfies $a/b \leq g(S)$" is that otherwise if there was an $(a,b)> g(S)$, then we could build an $(x,y)\in S$ such that $x/y$ is as large as wanted and therefore larger than $\gamma$? $\endgroup$ – user101859 Mar 20 at 18:57
  • $\begingroup$ No, this follows directly from the definition of $g(S)$. Your argument explains why $g(S) < \gamma$. $\endgroup$ – Yuval Filmus Mar 20 at 19:09
5
$\begingroup$

Every variable except $\gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $\gamma>0$, there is a sequence of rational numbers $\dfrac{a_1}{b_1}\lt\dfrac{a_2}{b_2}\lt\dfrac{a_3}{b_3}\lt\cdots \lt\gamma$ such that $\dfrac{a_i}{b_i}$ is nearer to $\gamma$ than any other rational number smaller than $\gamma$ whose denominator is less than $b_i$.


It turns out that the pumping lemma does work!

For the sake of contradiction, let $p$ be the pumping length of $L$ as a context-free language. Let $s=a^{a_p}b^{b_p}$, a word that is $L$ but "barely". Note that $|s|>b_p\ge p$. Consider $s=uvwxy$, where $|vx|> 1$ and $s_n=uv^nwx^ny\in L$ for all $n\ge0$.

Let $t_a$ and $t_b$ be the number of $a$s and $b$s in $vx$ respectively.

  • If $t_b=0$ or $\dfrac{t_a}{t_b}\gt\gamma$, for $n$ large enough, the ratio of the number of $a$s to that of $b$s in $s_n$ will be larger than $\gamma$, i.e., $s_n\not\in L$.
  • Otherwise, $\dfrac{t_a}{t_b}\lt\gamma$. Since $t_b<b_p$, $\dfrac{t_a}{t_b}\lt \dfrac{a_p}{b_p}$. Hence, $\dfrac{a_p-t_a}{b_p-t_b}>\dfrac{a_p}{b_p}$ Since $b_p-t_b<b_p$, $\dfrac{a_p-t_a}{b_p-t_b}>\gamma,$ which says that $s_0\not\in L$.

The above contradiction shows that $L$ cannot be context-free.


Here are two related easier exercises.

Exercise 1. Show that $L_\gamma=\{a^{\lfloor i \gamma\rfloor}: i\in\Bbb N\}$ is not context-free where $\gamma$ is an irrational number.

Exercise 2. Show that $L_\gamma=\{a^ib^j: i \leq j \gamma, i \ge0, j\ge 0\}$ is context-free where $\gamma$ is a rational number.

$\endgroup$
  • $\begingroup$ The property in the answer can be proved simply by selecting all rational numbers that is nearer to $\gamma$ than all previous numbers in the list of all rational numbers that are smaller than $\gamma$ in the order of increasing denominators and, for the same denominators, in increasing order. $\endgroup$ – Apass.Jack Mar 20 at 19:45
  • $\begingroup$ The usual construction is to take convergents of the continued fraction. $\endgroup$ – Yuval Filmus Mar 20 at 20:03
  • $\begingroup$ @YuvalFilmus Yes, I agree. On the other hand, that almost-one-line proof is much simpler and accessible. (the "increasing order" in my last message should be "decreasing order".) $\endgroup$ – Apass.Jack Mar 20 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy