A linguagem unária com o contexto de poder polinomial é sensível?

eu suponho que $\Sigma = \{a\}$.

Prove ou refute: para cada polinômio $p(n)$ com coeficientes em $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ é uma linguagem sensível ao contexto.

Parece que é uma linguagem sensível ao contexto. Eu acho que criar LBA ou gramática sensível ao contexto não é fácil para esse idioma. Posso provar isso com a propriedade de fechamento da CSL, por exemplo, como complemento? Alguém pode me ajudar a provar, por exemplo$L_1 = \{a^{n^7+n^5+n^3+n^2+1} | n\in \mathbb{N}\}$é sensível ao contexto. Talvez eu possa ter uma idéia disso para provar minha primeira pergunta.

Não é verdade para polinômios lineares. Por exemplo, deixe$p(n)$ estar $3n+2$, então L é gerado pela gramática regular 'S -> aaaS | aa '. [a menos que você queira dizer 'no máximo sensível ao contexto', não 'exatamente sensível ao contexto']

The Pumping Lemmas for both regular and context-free grammars seem to imply that any language over a 1-letter alphabet can be decomposed into a (not necessarily disjoint) union of sub-languages corresponding to linear polynomials. If the set of linear polynomials in question can be made finite (which I suspect must be true, but I can't prove or disprove off the top of my head [and I am not sure it even matters]), then any higher-degree polynomial must take on values not achieved by any polynomial in the linear set, in which case such languages must be at least context-sensitive.

Also: A strategy for building a context-sensitive grammar for a polynomial language over one alphabet is to construct a sequence of $k$ sub-grammars, each of which takes $m$ consecutive $a$'s and transforms it into $b_km+c_k$ consecutivo $a$s para algumas constantes $b_k$, $c_k$ [pense em "Método de Horner"] e depois em cascata para a próxima sub-gramática.

Então, se você quer dizer "no máximo sensível ao contexto", então sim.