Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$

Question

I am looking for an unrestricted grammar which generates the following language:

$\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$

That is, words like $a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$'}$.

Answer 1

If the grammar can be really unrestricted (meaning the variables are allowed to totally disappear) the design of the grammar is not complicated.

Start with left and right boundaries. Assume the string already is of the wanted form (with boundaries): $L a^1\#a^2\#\dots\#a^k R$.

We can obtain the next string by adding one $a$ to each of the segments of $a$'s. We do this by having a symbol $W$ walking over the string from left to right while adding an $a$ after each $\#$. Basically this uses the production rule $W\#\to \#aW$. Of course $W$ starts at the left $L$ and disappears at the right $R$. Of course when the walker starts an extra $a\#$ at the left end must be generated.

A little tuning will make this work. At the end check that you did not forget to generate the string $a$.