-1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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
    Commented May 22, 2017 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
    Commented May 22, 2017 at 22:23
  • $\begingroup$ Very close to the language $a^{n^2}$ $\endgroup$
    – Hendrik Jan
    Commented May 23, 2017 at 3:27

2 Answers 2

Reset to default
3
$\begingroup$

Hint:

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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