Język obejmujący liczbę niewymierną nie jest CFL

Pracuję nad ciężkim ćwiczeniem w podręczniku i po prostu nie mogę wymyślić, jak postępować. Oto problem. Załóżmy, że mamy język gdzie jest liczbą nieracjonalną. Jak mam udowodnić, że nie jest językiem bezkontekstowym?$L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$$\gamma$$L$

W przypadku, gdy jest racjonalna, całkiem łatwo jest zbudować gramatykę, która akceptuje język. Ale ponieważ jest irracjonalna, tak naprawdę nie wiem, co robić. Nie wygląda na to, żeby działał tu któryś z pompujących lematów. Być może twierdzenie Parikha działałoby tutaj, ponieważ intuicyjnie wydawałoby się, że ten język nie ma towarzyszącego półiliniowego obrazu Parikha.$\gamma$$\gamma$

Ćwiczenie pochodzi z „Drugiego kursu języków formalnych i teorii automatów” Jeffrey'a Shallita, ćwiczenie 25 rozdziału 4.

Byłbym naprawdę wdzięczny za wszelką pomoc lub trąci we właściwym kierunku. Dziękuję Ci!

Zgodnie z twierdzeniem Parikha, gdyby $L$ były pozbawione kontekstu, wówczas zbiór $M = \{(a,b) : a \leq \gamma b \}$ byłby półliniowy, to znaczy byłby sumą skończonej liczby zbiorów $S = u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_\ell$ , dla niektórych $u_i = (a_i,b_i)$ .

Oczywiście $u_0 \in M$ , a ponadto $u_i \in M$ dla każdego $i > 0$ , gdyż w przeciwnym razie $u_0 + N u_i \notin M$ o wystarczająco dużej $N$ . Dlatego $g(S) := \max(a_0/b_0,\ldots,a_\ell/b_\ell) < \gamma$ (ponieważ $g(S)$jest racjonalny). Oznacza to, że każda $(a,b) \in S$ spełnia .$a/b \leq g(S)$

Załóżmy teraz, że jest sumą i zdefiniuj . Powyższe pokazuje, że każdy w związku spełnia , i otrzymujemy sprzeczność, ponieważ$M$$S^{(1)},\ldots,S^{(m)}$$g = \max(g(S^{(1)}),\ldots,g(S^{(m)})) < \gamma$$(a,b)$$a/b \leq g < \gamma$$\sup \{ a/b : (a,b) \in M \} = \gamma$ .

---

Gdy $\gamma$ jest racjonalne, dowód się nie udaje i rzeczywiście $M$ jest półliniowy:

$$\{ (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).$$ Rzeczywiście, z konstrukcji, każda para$(a,b)$po prawej stronie spełnia$a \leq \tfrac{s}{t} b$(ponieważ$s = \tfrac{s}{t} t$). Odwrotnie, załóżmy, że$a \leq \frac{s}{t} b$. Podczas≥aib≥t, odejmowanie(s,t),z(a,b). W końcua<s(ponieważb<toznaczaa≤s$a \geq s$$b \geq t$$(s,t)$$(a,b)$$a < s$$b < t$$a \leq \frac{s}{t}b < s$). Ponieważ$a \leq \frac{s}{t} b$, koniecznie$b \geq \lceil \tfrac{t}{s} a \rceil$. W związku z tym można odjąć$(0,1)$z$(a,b)$aż do osiągnięcia$(a,\lceil \tfrac{t}{s} a \rceil)$.

Każda zmienna oprócz $\gamma$ w tej odpowiedzi oznacza dodatnią liczbę całkowitą. Dobrze wiadomo, że przy irracjonalnym $\gamma>0$ istnieje ciąg liczb wymiernych $\dfrac{a_1}{b_1}\lt\dfrac{a_2}{b_2}\lt\dfrac{a_3}{b_3}\lt\cdots \lt\gamma$tak, że$\dfrac{a_i}{b_i}$ jest bliżej$\gamma$niż jakikolwiek inny numer racjonalnego mniejszej niż$\gamma$, którego mianownik jest mniejszy niż$b_i$.

---

Okazuje się, że lemat pompujący działa!

Ze względu na sprzeczność niech $p$ będzie długością $L$ jako języka bezkontekstowego. Niech $s=a^{a_p}b^{b_p}$ , słowo, które jest $L$ ale „ledwo”. Zauważ, że $|s|>b_p\ge p$ . Rozważ $s=uvwxy$ , gdzie $|vx|> 1$ i $s_n=uv^nwx^ny\in L$ dla wszystkich$n\ge0$ .

Niech $t_a$ i $t_b$ będą liczbą $a$ si i $b$ s w $vx$ .

• Jeśli $t_b=0$ lub $\dfrac{t_a}{t_b}\gt\gamma$dla$n$wystarczająco duży, to stosunek ilości$a$S jak w$b$s w$s_n$będzie większa niż$\gamma$, to znaczy$s_n\not\in L$.
• W przeciwnym razie, $\dfrac{t_a}{t_b}\lt\gamma$. Ponieważ$t_b<b_p$,$\dfrac{t_a}{t_b}\lt \dfrac{a_p}{b_p}$ . Stąd s-t$\dfrac{a_p-t_a}{b_p-t_b}>\dfrac{a_p}{b_p}$ Ponieważ$b_p-t_b<b_p$,$\dfrac{a_p-t_a}{b_p-t_b}>\gamma,$ który mówi, że$s_0\not\in L$.

Powyższa sprzeczność pokazuje, że $L$ nie może być pozbawiony kontekstu.

---

Oto dwa powiązane łatwiejsze ćwiczenia.

Ćwiczenie 1. Pokaż, że $L_\gamma=\{a^{\lfloor i \gamma\rfloor}: i\in\Bbb N\}$ nie jest pozbawione kontekstu, gdzie $\gamma$ jest liczbą niewymierną.

Ćwiczenie 2. Pokaż, że $L_\gamma=\{a^ib^j: i \leq j \gamma, i \ge0, j\ge 0\}$ jest pozbawione kontekstu, gdzie $\gamma$ jest liczbą wymierną.