Question

Convert the following regular expressions to NFAs using the procedure given in Theorem 1.54. In all parts,$\mathit{\Sigma }\mathbf{=}\left\{a,b\right\}$.

$$\begin{gathered} \mathit{a}\mathbf{.}\mathbf{ }\mathbf{ }\mathbf{ }\mathit{a}\mathbf{\left(}\mathit{a}\mathit{b}\mathit{b}\mathbf{\right)}\mathbf{*}\mathbf{\cup }\mathit{b} \\ \mathit{b}\mathbf{.}\mathbf{ }\mathbf{ }\mathbf{ }\mathbf{ }{\mathit{a}}^{\mathbf{+}}\mathbf{\cup }\mathbf{(}\mathbf{a}\mathbf{b}{\mathbf{)}}^{\mathbf{+}} \\ \mathit{c}\mathbf{.}\mathbf{ }\mathbf{ }\mathbf{ }\mathbf{ }\mathbf{(}\mathit{a}\mathbf{\cup }{\mathit{b}}^{\mathbf{+}}\mathbf{)}{\mathit{a}}^{\mathbf{+}}{\mathit{b}}^{\mathbf{+}} \end{gathered}$$

Short answer

(a) There are following for the given regular expression

(b) There are following for the given regular expression

(c) There are following for the given regular expression

Step-by-step solution

To Regular the expression state  a(abb)*∪b

(a) Given regular expression

$R=a\left(abb\right)*\cup b$over $\sum =\{a,b\}$.

To convert this regular expression into by the following steps:

To Regular the Expression state  a+∪(ab)+

(b) Given regular expression is

$R=a^{+}\cup (ab{)}^{+}$over $\sum =\{a,b\}$.

Now we have to convert this regular expression into by the following steps.

To Regular the Expression state (a∪b+)a+b+

(c) Given regular expression is $R=(a\cup b^{+})a^{+}{b}^{+}$over .

Now we have to convert this regular expression into by the following steps