0
$\begingroup$

This question already has an answer here:

Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? I think it is, but I could not find a way to prove it by using push down automaton or any other way.

$\endgroup$

marked as duplicate by Luke Mathieson, David Richerby, Ran G., Juho, Rick Decker Nov 1 '15 at 17:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ Since you were not able to prove the statement, what have you tried towards disproving it? $\endgroup$ – Raphael Nov 1 '15 at 10:21
1
$\begingroup$

A unary language (a subset of $a^*$) is context-free iff it is regular. This is a special case of Parikh's theorem. It is not too hard to show that a unary language $L$ is regular if and only if there exist $n,m$ such that for all $N \geq n$, $a^N \in L$ iff $a^{N+m} \in L$. See if this condition holds for your language.

$\endgroup$

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