patternMinor
Context-free grammar for $\{ a^n b^m a^{n+m} \}$
Viewed 0 times
contextgrammarforfree
Problem
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.
$\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.
Solution
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:
Notice that once you start adding $b$, you cannot go back to adding only $a$... so we need a new nonterminal:
Since the empty string is in your language, add another production to allow $B$ to generate the empty string. So we get:
The first, working from the outside, rule is straightforward:
S := aSaNotice that once you start adding $b$, you cannot go back to adding only $a$... so we need a new nonterminal:
S := B
B := bBaSince 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 | -Code Snippets
S := B
B := bBaS := aSa | B
B := bBa | -Context
StackExchange Computer Science Q#2127, answer score: 9
Revisions (0)
No revisions yet.