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.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Since you were not able to prove the statement, what have you tried towards disproving it? $\endgroup$– Raphael ♦Nov 1, 2015 at 10:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Nov 1, 2015 at 7:26