patternMinor
Language involving irrational number is not a CFL
Viewed 0 times
cflnumberinvolvingirrationallanguagenot
Problem
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!
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!
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#105836, answer score: 7
Revisions (0)
No revisions yet.