Use the construction in the proof of Theorem 1.45 to give the state diagrams of NFAs recognizing the union of the languages described in

a. Exercises 1.6a and 1.6b.

b. Exercises 1.6c and 1.6f

Use Theorem 1.45 which states the union of regular languages to construct state diagrams of NFA of the given languages.

Consider the given languages ,

$$\begin{gathered} L_1=\left\{w\right|w \text{startwith1\hspace{0.05em}andfinishwith\hspace{0.05em}a} 0\} \\ {L}_2=\{w|w u\text{singatleastthree1s}\}\text{on}\sum =\left\{0,1\right\} \end{gathered}$$.

Let $M_1\text{and}{M}_2$be the NFAs recognize the languages $L_1\text{and}{L}_2$respectively.

The union of the language can be defined as, $L=L_1\cup L_2$and $M$be the NFA that recognizes $L$.

The state diagram of $M_1$is as follows,

The state diagram of M₂ is as follows,

Therefore, the state diagram of M is as follows,

Consider the languages,

$L_1=\left\{w\right|w\text{containsthesubstring}0101i.e,w=x0101y\text{forsome}x\text{and}y\}on\sum =\{0,1\}$

$L_1=\left\{w\right|w\text{doesn'tcontainthesubstring}110\}\text{on}\sum =\{0,1\}$.

Let $M_1\text{and}{M}_2$be the NFAs that recognize the languages $L_1\text{and}{L}_2$respectively.

The union of two languages is , $L=L_1\cup L_2$ and it is recognized by the NFA $M$.

The state diagram of $M_1$is as follows,

The state diagram of $M_2$is as follows,

Therefore the state diagram of $M$is as follows,