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

  • $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ – dkaeae Dec 3 '18 at 16:09
  • $\begingroup$ 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! $\endgroup$ – user97180 Dec 3 '18 at 17:40

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.