0
$\begingroup$

My Introduction to Computation Theory professor talked about how we can write more general grammars (called unrestricted grammars) for languages that are not context-free. For example, the language: $\{0^{2^n} : n\geq0\}$ is not context-free, so it cannot be generated by a context-free grammar.

I am wondering if the language: $\{0^{n^2} : n\ge0\}$ is also not context-free, and what could be the grammar for it?

For this language, we would have to generate $n^2$ zeroes, which seems awkward and difficult to put into grammar form.

Improve this question
$\endgroup$
  • $\begingroup$ Have you seen: context free grammar with words of length $n^2$ or $n^3$ $\endgroup$ – Evil Nov 30 '17 at 4:23
  • $\begingroup$ Here is $2^n$ case, $a^{n^2}$. A little search does magic. $\endgroup$ – Evil Nov 30 '17 at 7:05
  • $\begingroup$ @Community Please change the "This question already has an answer here" into the second suggestion cited by Evil: cs.stackexchange.com/q/71567/4287 The question is not whether the language is context-free, but how it has a grammar "Is there a grammar (not necessarily context-free) that generates n^2 zeroes?" $\endgroup$ – Hendrik Jan Nov 30 '17 at 15:17
  • $\begingroup$ @HendrikJan The question is both of those things. One of them is an exact duplicate and the other is the reason we shouldn't have two separate questions bundled into one. $\endgroup$ – David Richerby Nov 30 '17 at 15:44

Browse other questions tagged or ask your own question.