Ist eine unäre Sprache mit Polynomkraft kontextsensitiv?

Ich nehme an, dass .$\Sigma = \{a\}$

Beweisen oder widerlegen: Für jedes Polynom mit Koeffizienten in gilt L = \ {a ^ {p (n)} \; | \; n \ in \ mathbb {N} \} ist eine kontextsensitive Sprache.$p(n)$$\mathbb{N}$$L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$

Es scheint, dass es eine kontextsensitive Sprache ist. Ich denke, LBA oder kontextsensitive Grammatik ist für diese Sprache nicht einfach. Kann ich dies mit der Schließungseigenschaft von CSL zum Beispiel wie Komplement beweisen? Kann mir jemand helfen, zum Beispiel L_1 = \ {a ^ {n ^ 7 + n ^ 5 + n ^ 3 + n ^ 2 + 1} | zu beweisen n \ in \ mathbb {N} \}$L_1 = \{a^{n^7+n^5+n^3+n^2+1} | n\in \mathbb{N}\}$ ist kontextsensitiv. Vielleicht kann ich mir daraus eine Idee machen, um meine erste Frage zu beweisen.

Nicht wahr für lineare Polynome. Zum Beispiel ließ seine , dann L durch die regelmäßige Grammatik ‚S erzeugt wird -> AAAS | aa '. [es sei denn, Sie meinen "höchstens kontextsensitiv", nicht "genau kontextsensitiv"]$p(n)$$3n+2$

Die Pumping Lemmas für reguläre und kontextfreie Grammatiken scheinen zu implizieren, dass jede Sprache über einem 1-Buchstaben-Alphabet in eine (nicht unbedingt disjunkte) Vereinigung von Untersprachen zerlegt werden kann, die linearen Polynomen entsprechen. Wenn die Menge der fraglichen linearen Polynome endlich gemacht werden kann (was meiner Meinung nach wahr sein muss, aber ich kann es nicht beweisen oder widerlegen [und ich bin mir nicht sicher, ob es überhaupt wichtig ist] ), dann höher Gradpolynom muss Werte annehmen, die von keinem Polynom in der linearen Menge erreicht werden. In diesem Fall müssen solche Sprachen zumindest kontextsensitiv sein.

Außerdem: Eine Strategie zum Erstellen einer kontextsensitiven Grammatik für eine Polynomsprache über ein Alphabet besteht darin, eine Folge von , von denen jede aufeinanderfolgende 's nimmt und sie für einige in aufeinanderfolgende s Konstanten , [denken Sie an "Horners Methode"] und dann 'Kaskaden' zur nächsten .$k$$m$$a$$b_km+c_k$$a$$b_k$$c_k$

Wenn Sie also "höchstens kontextsensitiv" meinen, dann ja.