S-grammar for this regular expression

Question

Given this regular expression:

$r = a a^* b + b^* c b$

I think this is the simple grammar, but I was getting a little lost with the productions:

$S \rightarrow S_1 | S_2$

$S_1 \rightarrow a A b$

$A \rightarrow a A | a$

$S_2 \rightarrow b S_2 | c b$

Answer 1

Write $r = a a^* b + b^* c b = (a a^* + b^* c )b$, then write a production for each 'component':

$S \rightarrow P b$

$P \rightarrow Q_1 | Q_2 $

$Q_1 \rightarrow a | Q_1 a$

$Q_2 \rightarrow c | b Q_2 $