La langue impliquant un numéro irrationnel n'est pas une LFC

Je travaille à travers un exercice difficile dans un manuel, et je n'arrive pas à comprendre comment procéder. Voici le problème. Supposons que nous ayons le langage $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ où $\gamma$ est un certain nombre irrationnel. Comment pourrais-je prouver que $L$ n'est pas un langage sans contexte?

Dans le cas où $\gamma$ est rationnel, il est assez facile de construire une grammaire qui accepte le langage. Mais parce que $\gamma$ est irrationnel, je ne sais pas vraiment quoi faire. Il ne semble pas que les lemmes de pompage fonctionnent ici. Peut-être que le théorème de Parikh fonctionnerait ici, car il semblerait intuitivement que cette langue n'a pas d'image parikh semi-linéaire d'accompagnement.

Cet exercice est tiré de "Un deuxième cours en langues formelles et théorie des automates" de Jeffrey Shallit, exercice 25 du chapitre 4.

J'apprécierais vraiment toute aide ou coup de coude dans la bonne direction. Je vous remercie!

Selon le théorème de Parikh, si $L$ était hors contexte, alors l'ensemble $M = \{(a,b) : a \leq \gamma b \}$ serait semi-linéaire, c'est-à-dire qu'il serait l'union d'un nombre fini d'ensembles de la forme $S = u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_\ell$ , pour certains $u_i = (a_i,b_i)$ .

Evidemment $u_0 \in M$ , et de plus $u_i \in M$ pour chaque $i > 0$ , car sinon $u_0 + N u_i \notin M$ pour $N$ assez grand . Donc $g(S) := \max(a_0/b_0,\ldots,a_\ell/b_\ell) < \gamma$ (puisque $g(S)$ est rationnel). Cela signifie que chaque $(a,b) \in S$ satisfait$a/b \leq g(S)$ .

Supposons maintenant que $M$ est l'union de $S^{(1)},\ldots,S^{(m)}$ , et définissons $g = \max(g(S^{(1)}),\ldots,g(S^{(m)})) < \gamma$ . Ce qui précède montre que tout $(a,b)$ dans l'union satisfait $a/b \leq g < \gamma$ , et nous obtenons une contradiction, puisque $\sup \{ a/b : (a,b) \in M \} = \gamma$ .

---

Lorsque $\gamma$ est rationnel, la preuve échoue, et en effet $M$ est semi-linéaire:

$$\{ (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).$$ En effet, par construction, toute paire$(a,b)$ du côté droit satisfait $a \leq \tfrac{s}{t} b$(puisque$s = \tfrac{s}{t} t$). Inversement, supposons que$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)$.

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.