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

Problem Detail: 

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.

Asked By : user1594

Answered By : Patrick87

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2127