Let $G$ be the grammar

$G$: $\{\begin{array}{c}\text{:}[SaS|bA|a]\\ AaS|bA|b.\end{array}$

a$)$ Use Theorem $6\mathrm{.}3\mathrm{.}1$ to build an NFA M that accepts L$($G$).$

Theorem $6\mathrm{.}3\mathrm{.}1$

Let $G=(V,,P,S)$ be a regular grammar. Define the NFA $M=(Q,,,S,F)$ as follows:

i$)Q=\{\begin{array}{ccc}V\{Z\}& \text{w}\text{h}\text{e}\text{r}\text{e}Z!\text{i}\text{n}\text{V}\text{,}ifP\text{c}\text{o}\text{n}\text{t}\text{a}\text{i}\text{n}\text{s}\text{a}\text{r}\text{u}\text{l}\text{e}& Aa\\ v& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\text{.}& \end{array}$

ii$)(A,a)=B$ whenever $A$aBinP

$(A,a)=Z$ whenever $A$ainP.

iii$)F=\{\begin{array}{ccc}\{A|AinA\}\{Z\}& if& \text{Z}\text{i}\text{n}\text{Q}\\ \{A|AinP\}& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\text{.}& \end{array}$

Then $L(M)=L(G).$