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.

  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby May 22 '17 at 17:02
  • $\begingroup$ 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. $\endgroup$ – Sotiris Dimitras May 22 '17 at 22:23
  • $\begingroup$ Very close to the language $a^{n^2}$ $\endgroup$ – Hendrik Jan May 23 '17 at 3:27




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
  • $\begingroup$ Nice. Glad you figured it out and thanks for posting it as an answer! $\endgroup$ – David Richerby May 23 '17 at 8:27

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.