Question

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

Short answer

a.

b.

Step-by-step solution

Explain the given information

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

(a) Give the state diagrams of NFAs recognizing the union of the 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,

(b) Give the state diagrams of NFAs recognizing the union of the languages

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,