Eine Sprache mit irrationaler Zahl ist keine CFL

Ich arbeite an einer harten Übung in einem Lehrbuch und kann einfach nicht herausfinden, wie ich vorgehen soll. Hier ist das Problem. Angenommen, wir haben die Sprache wobei eine irrationale Zahl ist. Wie würde ich beweisen, dass keine kontextfreie Sprache ist?$L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$$\gamma$$L$

In dem Fall, in dem rational ist, ist es ziemlich einfach, eine Grammatik zu erstellen, die die Sprache akzeptiert. Aber weil irrational ist, weiß ich nicht wirklich, was ich tun soll. Es sieht nicht so aus, als würde eines der pumpenden Deckspelzen hier funktionieren. Vielleicht würde der Satz von Parikh hier funktionieren, da es intuitiv so aussieht, als hätte diese Sprache kein semilineares Parikh-Bild.$\gamma$$\gamma$

Diese Übung stammt aus "Ein zweiter Kurs in formalen Sprachen und Automatentheorie" von Jeffrey Shallit, Übung 25 von Kapitel 4.

Ich würde mich über jede Hilfe oder einen Anstoß in die richtige Richtung sehr freuen. Vielen Dank!

Nach dem Satz von Parikh wäre die Menge semilinear , wenn kontextfrei wäre, dh es wäre die Vereinigung endlich vieler Mengen der Form , für einige .$L$$M = \{(a,b) : a \leq \gamma b \}$$S = u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_\ell$$u_i = (a_i,b_i)$

Offensichtlich , und darüber hinaus für jedes , da sonst für groß genug , um . Daher ist (da rational ist). Dies bedeutet, dass jedes erfüllt .$u_0 \in M$$u_i \in M$$i > 0$$u_0 + N u_i \notin M$$N$$g(S) := \max(a_0/b_0,\ldots,a_\ell/b_\ell) < \gamma$$g(S)$$(a,b) \in S$$a/b \leq g(S)$

Nehmen wir nun an, dass die Vereinigung von , und definieren Sie . Das Vorstehende zeigt, dass jedes in der Vereinigung erfüllt , und wir erhalten einen Widerspruch, da .$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$

Wenn rational ist, schlägt der Beweis fehl, und tatsächlich ist semilinear: Tatsächlich erfüllt konstruktionsbedingt jedes Paar auf der rechten Seite (da ). Nehmen wir umgekehrt an, dass . Während und , subtrahieren Sie von . Schließlich (da impliziert$\gamma$$M$

Jede Variable außer in dieser Antwort steht für eine positive ganze Zahl. Es ist bekannt, dass es bei einem irrationalen eine Folge von rationalen Zahlen gibt so dass näher an als jede andere rationale Zahl kleiner als deren Nenner kleiner als .$\gamma$$\gamma>0$$\dfrac{a_1}{b_1}\lt\dfrac{a_2}{b_2}\lt\dfrac{a_3}{b_3}\lt\cdots \lt\gamma$$\dfrac{a_i}{b_i}$$\gamma$$\gamma$$b_i$

Es stellt sich heraus, dass das Pump-Lemma funktioniert!

Aus Gründen des Widerspruchs sei die Pumplänge von als kontextfreie Sprache. Sei , ein Wort, das aber "kaum". Beachten Sie, dass . Betrachten Sie , wobei und für alle .$p$$L$$s=a^{a_p}b^{b_p}$$L$$|s|>b_p\ge p$$s=uvwxy$$|vx|> 1$$s_n=uv^nwx^ny\in L$$n\ge0$

Sei und die Anzahl von s und s in .$t_a$$t_b$$a$$b$$vx$

• Wenn oder für groß genug ist, ist das Verhältnis der Anzahl von s zu der von s in größer als , dh .$t_b=0$$\dfrac{t_a}{t_b}\gt\gamma$$n$$a$$b$$s_n$$\gamma$$s_n\not\in L$
• Andernfalls . Da , . Daher ist Da , was besagt, dass .$\dfrac{t_a}{t_b}\lt\gamma$$t_b<b_p$$\dfrac{t_a}{t_b}\lt \dfrac{a_p}{b_p}$$\dfrac{a_p-t_a}{b_p-t_b}>\dfrac{a_p}{b_p}$$b_p-t_b<b_p$$\dfrac{a_p-t_a}{b_p-t_b}>\gamma,$$s_0\not\in L$

Der obige Widerspruch zeigt, dass nicht kontextfrei sein kann.$L$

Hier sind zwei verwandte einfachere Übungen.

Übung 1. Zeigen Sie, dass nicht kontextfrei ist, wenn eine irrationale Zahl ist.$L_\gamma=\{a^{\lfloor i \gamma\rfloor}: i\in\Bbb N\}$$\gamma$

Aufgabe 2. Zeigen Sie, dass kontextfrei ist, wobei eine rationale Zahl ist.$L_\gamma=\{a^ib^j: i \leq j \gamma, i \ge0, j\ge 0\}$$\gamma$