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?

  • 3
    $\begingroup$ 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. $\endgroup$ – Raphael Aug 11 '14 at 20:58

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.

  • $\begingroup$ 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? $\endgroup$ – Mouh Khosin Aug 11 '14 at 18:42
  • $\begingroup$ @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 $\endgroup$ – Rick Decker Aug 14 '14 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.