# Context-free grammar for $\{ a^n b^m a^{n+m} \}$

I've got a problem with this task. I should declare a context-free grammar for this language:

$\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$

My idea is: We need a start symbol, for example $S$. I know that I can generate the first $a$ and the last $a$ by $S \to a a$. I don't know what is the next idea to solve this task.

• Exercise 6.2.a, due May 31st. – Raphael May 30 '12 at 8:01
• @Raphael What's the point of the above comment? If it's not constructive, please delete it (and this too). – Patrick87 May 30 '12 at 14:17
• @Patrick87: It serves to document a) the sources of the questions user1594/1671 has been posting and b) that they have dumping their homework. People might want to hold back on full answers until after the due date. – Raphael May 30 '12 at 14:40
• @Raphael This question seems too generic to require a reference; anybody could come up with such a question, so attribution isn't necessary. Regarding the date... alright, you can remove it after May 31, if you remember. – Patrick87 May 30 '12 at 16:24
• @Patrick87: I hope my meta answer here explains my reasons for the comment sufficiently. Please remove all but the first comment if you agree. – Raphael May 30 '12 at 20:38

First, rewrite $a^nb^ma^{n+m}$ as $a^nb^ma^ma^n$. Now, from the outside in, you need rules to (1) add an $a$ to the front and back of your strings, and (2) to add $b$ to the front and $a$ to the back. It's also helpful to imagine building strings from the inside out... you can either add a $b$ to the front and an $a$ to the back, or an $a$ to both ends.

The first, working from the outside, rule is straightforward:

S := aSa


Notice that once you start adding $b$, you cannot go back to adding only $a$... so we need a new nonterminal:

S := B
B := bBa


Since the empty string is in your language, add another production to allow $B$ to generate the empty string. So we get:

S := aSa | B
B := bBa | -

• i've got a question you notice three times S. Do you mean that we've got only two nonterminal S and A or three with B too? – user1594 May 28 '12 at 15:39
• @user1594 Edited to clarify. One grammar, two nonterminals. – Patrick87 May 28 '12 at 15:48
• i've understand it but can we also prove it except by trying? – user1594 May 28 '12 at 16:28
• @user1594: Of course. For one direction you will have to do induction over the number of derivation steps (or structural induction) and for the other direction nested induction over $n$ and $m$ (some tricks are possible). – Raphael May 28 '12 at 16:41
• How would see the induction i can't imagine it. Thanks – user1594 May 29 '12 at 23:12

Hint: Develop grammars for the simple languages $\{a^nb^n \mid n \in \mathbb{N}\}$ and $\{a^nb^m \mid m,n \in \mathbb{N}\}$, respectively, and combine (variations of) them to generate your $L$.

• Why the downvote? – Raphael May 28 '12 at 12:15