Question

Use the procedure described in Lemma 1.55 to convert the following regular expressions to nondeterministic finite automata.

$$\begin{gathered} a.(0\cup 1)*000(0\cup 1)* \\ b.\left(\right(\left(00\right)*\left(11\right))\cup 01)* \\ c.\varnothing * \end{gathered}$$

Short answer

As per the above question the procedure for Lemma 1.55 use to convert regular expression to nondeterministic finite automata.

Step-by-step solution

To Convert Regular Expression

As per the above question, the procedure for Lemma 1.55 is used to convert regular expressions to nondeterministic finite automata. To, convert lemma 1.55 calculations is to follow, and count nondeterministic information is written below step-2 as below.

To the procedure described in Lemma 1.55 for regular expression

a. $\left(0+1\right)*000\left(0+1\right)*$

Consider the regular expression $R=\left(0\cup 1\right)*000\left(0\cup 1\right)*$.

Now, construct an NFA from this regular expression in the following procedure:

The regular expression of 0

The regular expression of 1

The regular expression of $(0\cup 1)$

The regular expression of $(0\cup 1)*$

The regular expression of 000

The regular expression of $(0\cup 1)*000(0\cup 1)*$

To the procedure described in Lemma 1.55 for regular expression

$\left(\left(00\right)*11+01\right)*$

Consider the regular expression $R=\left(\right(\left(00\right)*\left(11\right))\cup (01\left)\right)*$ .

Now, construct the NFA from this regular expression in the following procedure:

The regular expression of 0

The regular expression of 1

The regular expression of 00

The regular expression of $\left(00\right)*$

The regular expression of 11

The regular expression of $\left(00\right)*11$

The regular expression of 01

The regular expression of$\left(\right(\left(00\right)*\left(11\right))\cup (01\left)\right)$

The regular expression of $\left(\right(\left(00\right)*\left(11\right))\cup (01\left)\right)*$

To the procedure described in Lemma 1.55 for regular expression

$\varnothing *=\epsilon$

Let the normal expression $R=\varnothing *$ .

An unfilled format's closure is indeed an empty string. i.e., $\varnothing *=\left\{e\right\}$. The NFA for the regular expression is as follows: