8
$\begingroup$

I suppose that $\Sigma = \{a\}$.

Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language.

It seems that it is a context sensitive language. I guess making LBA or context sensitive grammar is not easy for this language. Can I prove this with closure property of CSL for example like complement? Can any one help me to prove for instance $L_1 = \{a^{n^7+n^5+n^3+n^2+1} | n\in \mathbb{N}\}$ is context sensitive. Maybe I can get an idea from this to prove my first question.

| cite | improve this question | |
$\endgroup$
-1
$\begingroup$

Not true for linear polynomials. E.g let $p(n)$ be $3n+2$, then L is generated by the regular grammar 'S --> aaaS | aa'. [unless you mean 'at most context-sensitive', not 'exactly context-sensitive']

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$ consecutive $a$s for some constants $b_k$, $c_k$ [think "Horner's Method"] and then 'cascades' to the next sub-grammar.

So if you mean 'at most context-sensitive', then yes.

| cite | improve this answer | |
$\endgroup$
  • 8
    $\begingroup$ That's not what context-sensitive means (at least not under the standard definition). Every context-free language is also a context-sensitive language. The standard definition says that $L$ is a context-sensitive language if there exists a context-sensitive grammar for $L$; there's no requirement that $L$ must be not-context-free. Perhaps you can adapt the 3rd paragraph to provide a proof of the claimed statement? I'm not quite clear about the details of what you're suggesting, though. How do you build such a sub-grammar? $\endgroup$ – D.W.♦ Jan 30 '17 at 19:04
  • 1
    $\begingroup$ A unary language $L$ is regular iff it is context-free iff the set $\{n : a^n \in L\}$ is eventually periodic. $\endgroup$ – Yuval Filmus Dec 27 '17 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.