# Unrestricted grammar to generate $a^{n(n+1)/2}$

I have been asked to find a grammar that will generate the language $a^{n(n+1)/2}$, where $n\ge1$ as an exercise. Any idea on how to set up such grammar? Any help would be appreciated.

• What did you try? Where did you get stuck? We're happy to help with conceptual questions but just solving homework-style exercises for you is unlikely to really help you. – David Richerby May 22 '17 at 17:02
• Mr David, At the very beginning I was trying to generate a grammar using the hint that was provided as an answer. However I thought of a different way to solve my problem and i was trying to figure out how to decrease the number of "a" into half. I have to apologize because I was not clear what I actually wanted to ask. Moreover, I figure out a way that could be solved and I posted as an answer at the question, as well as the unrestricted grammar. Thank you for your time. – Sotiris Dimitras May 22 '17 at 22:23
• Very close to the language $a^{n^2}$ – Hendrik Jan May 23 '17 at 3:27

Hint:

$\sum\limits_{n=1}^{m}n=\frac{m(m+1)}{2}$

I came up with an idea while trying to solve my question. The length of the input string should be n(n+1)/2 => (n^2 + n)/2. We know how to generate a unrestricted grammar for the language a^(n^2)b^n.In this problem, each b will be replaced by an a. Thus, the string's length will be (n^2 + n) . However we need half of this string. In order to Decrease the number of a , I changed the rules such as that a new symbol,D, would be created and it would be responsible for the deletion of an a. Basically the grammar looks like this:

• S -> LS'R
• S'-> XS'YB
• S'-> e
• BY-> YDB
• XY-> YaX
• aY-> Ya
• Xa-> aX
• LY-> DL
• DR-> RD
• XR-> R
• La-> aL
• BR-> Ra
• LR-> e
• Da-> e
• DY-> YD
• Nice. Glad you figured it out and thanks for posting it as an answer! – David Richerby May 23 '17 at 8:27