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
