L = { a^n b^2n a^(n+2) : n>=1 }

So I'm trying to construct the grammar and I'm getting stuck.Some example strings would be these (spaced out to help demonstrate the patterns):

a bb aaa

aa bbbb aaaa

aaa bbbbbb aaaaa

This is what I have so far....

S -> aXbbXaaa

XbbX -> bXbbXb

The first rule says that there will always be an a on the left side, 3 a's on the right, and 2 b's in the middle.

The second rule adds 2 b's to the middle for b^2n.

But I can't figure out a way to get the a's....

Any suggestions? I don't want the exact answer, but rather hints to lead me to a solution. Thanks in advance!

  • $\begingroup$ Well, I'm pretty sure there exists some grammar, no matter how ridiculously complex, because this is a homework question. Also, we haven't discussed the Pumping Lemma yet, so I doubt that route is the solution. However, thanks for the thoughts. It looks pretty unsolvable to me too! $\endgroup$ – Connal Sumlin Sep 23 '14 at 2:47
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Sep 23 '14 at 4:27

Hint: The language is not context-free. So you will need to employ a type of grammar that is more powerful. Context-sensitive grammars can do the job.

If you need guidance in how to build a context-sensitive grammar for such a language, you might want check a context-sensitive grammar for $a^nb^nc^n$.

| cite | improve this answer | |

It should be possible to use an attribute grammar to produce strings in your given language. Chapter 3 of the lecture notes provided here motivates attribute grammars using the language $L = \{a^n b^n c^n, n >= 1 \}$. The second attribute grammar for said language may be of particular interest to you

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