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

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'}$$.

• What have you tried? Where did you get stuck? – dkaeae Dec 3 '18 at 16:09
• I started with a rule such as S --> a#TPC, where T is the current marker, P is the previous marker and C is the counter to count the occurrences of a's in the language... however any rules I think of also generate strings that are not in the given language. So I am not sure where I am going wrong! – user97180 Dec 3 '18 at 17:40

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$$.