# Grammar for square numbers in unary

I have to write a grammar for the following language: $$\{1^{n^2} \mid n\geq 1 \}$$ I am having trouble figuring out the production rules. I was thinking of using the fact that $n^2$ can be written as the sum of first $n$ odd numbers but couldn't proceed any further.

• Your language is not context-free. What kind of grammar are you interested in? A context-sensitive grammar? – Yuval Filmus Feb 23 '16 at 16:05
• The following paper gives a context-sensitive grammar for $\{0^{F_n} : n \geq 0\}$, where $F_n$ is the $n$th Fibonacci paper: fq.math.ca/Scanned/31-1/mootha.pdf. Perhaps this is useful for you. – Yuval Filmus Feb 23 '16 at 16:08
• Context-free-grammar is out of question. As Yuval mentions you can write a context-sensitive grammar. First try to construct an LBA. That will help in understanding how you can go about writing CSG. – Shreesh Feb 23 '16 at 16:11
• Any kind of grammar would work but if a context-sensitive is possible, I would like that! I am looking at the paper. :) – Pranav Arora Feb 23 '16 at 16:19
• @YuvalFilmus: I looked at the paper but its too difficult for me currently. I doubt the above problem requires so many production rules. :/ – Pranav Arora Feb 23 '16 at 16:35

Let $B$ stand for the beginning marker, $A$ stands for a single 1 to be added later, $D$'s are copier markers and $E$ be the end marker. $F$, $G$, $I$, $H$ markers are used to properly generate all $A$'s. The following is not the most efficient grammar, but it will do.

Context free grammar rules:

$S \rightarrow BAFUE\ |\ \epsilon$
$U \rightarrow UD \ | \ D$

Non-contracting grammar rules:

$FD \rightarrow DG$
$AD \rightarrow D1A$
$1D \rightarrow D1$
$A1 \rightarrow 1A$
$BD \rightarrow BH$
$H1 \rightarrow 1H$
$HA\rightarrow AI$
$IA\rightarrow AI$
$IG \rightarrow AAF$

Now some non non-contracting rules:

$FE \rightarrow E$
$B \rightarrow \epsilon$
$AE \rightarrow E$
$E \rightarrow \epsilon$

Though this grammar has four non non-contracting rules, I have left them as it is, to help understanding. With a little effort we can convert it into a non-contracting grammar and then to a context-sensitive-grammar.

$IG \rightarrow AAF$ is the important rule, every time it adds two extra $AA$'s to be later substituted by 1's.

• I was not looking for most efficient grammar rules. I was interested in how we can use simple copy grammars and the fact that $n^2 = 1 + 3 + 5 ...$ to get a (sufficiently) easy grammar. – Shreesh Jan 1 '17 at 13:50
• I used non non-contracting to emphasize that what we really want are non-contracting rules and these rules are anomaly. – Shreesh Jan 4 '17 at 16:35

Imagine a head that walks over the sentential form and expands some non-terminals it finds. What should the head do?

Start with a single $A$ and the head to the left of it, i.e. $\circ A$. The head passed from left to right and expands every $A$ it finds to a $1$ and a new $A$ -- and the last $A$ spawns a a new $A$ and triggers that the head copies the last block of $1$s.

How do you move the head?

With rules of the form $\circ A \to A \circ$.

How do you control what the head does where?

Introduce marked copies of symbols. For instance, the last $A$ could be a $\hat A$.