# Language of a grammar

What's the language of following grammar?

$G: S \to S_1B$

$S_1 \to aS_1b$

$bB \to bbbB$

$aS_1b \to aa$

$B \to \lambda$

any hint or solution?

• What have you tried and where did you get stuck? This is not a homework-solving service and we can't help you with your underlying problem unless you give us more. – Raphael Aug 11 '14 at 20:58

## 1 Answer

Hint: Starting with $S\rightarrow S_1B$, do the $S_1$ derivation and then the $B$ part. Invoke $S_1\rightarrow aS_1b$ a certain number, $n$, times. What do you get? Then eliminate $S_1$ by using $aS_1b\rightarrow aa$. Now what do you have? Finally, use $bB\rightarrow bbbB$ some number, $m$ times (getting two more $b$s each time) and eventually erase the $B$. What's your final result? It should be fairly obvious, except for one special case.

• Dear @Decker, I get a^n aa b^n B. then by using (3) I get a^n aa^(n-1) bbb B... am I right? – Mouh Khosin Aug 11 '14 at 18:42
• @MouhKhosin. Almost. You have a typo: it should be $a^naab^{n-1}bbbB$. Also, you have the string $aa$ in the language. That's the special case I mentioned – Rick Decker Aug 14 '14 at 14:16