# Creating a grammar from the language

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!

• 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! – Connal Sumlin Sep 23 '14 at 2:47
• 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. – FrankW Sep 23 '14 at 4:27

## 2 Answers

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

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