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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.