Question

Use the construction in the proof of Theorem 1.47 to give the state diagrams of NFAs recognizing the concatenation of the languages described in

a. Exercises 1.6g and 1.6i.

b. Exercises 1.6b and 1.6m.

Short answer

(a) $L$is concatenation of $L_1$and $L_2$.

(b) $L$ is a union of $L_1$and $L_2$_.

Step-by-step solution

Explain the given information

Using construction theory, prove the Theorem 1.47. Construct the diagram NFA recognize the languages that describes concatenation of the languages given.

(a) Give the state diagram of NFA recognizing the concatenation of the languages.

Consider the languages $L_1=\left\{w|\text{thelengthof}w\text{isatmost}5\right\}\text{on}\sum =\left\{0,1\right\}$and $L_2=\left\{w|\text{alloddplaces}\text{of}w\text{isa}1\right\}\text{on}\sum =\left\{0,1\right\}$.

The NFA $M_1$recognizes the language $L_1$and the NFA $M_2$recognizes the language $L_2$.

The concatenation of the languages $L_1$and $L_2$
is represented as $L$.

The NFA $M_1$is as follows,

The NFA is as follows,

The state diagram that recognizes is as follows,

(b) Give the state diagram of NFA recognizing the concatenation of the languages. 

Consider that $L_1=\left\{w|w\text{carryatleastthree}1\text{s}\right\}\text{on}\sum =\left\{0.1\right\}$and $L_2=\left\{w|\text{alloddplacesofwisa}1\right\}\text{on}\sum =\left\{0,1\right\}$. The NFA $M_1$recognizes the language $L_1$and the NFA $M_2$recognizes the language $L_2$. The concatenation of the languages $L_1\text{and}{L}_2$is $L$that is recognized by the NFA $M$.

The NFA $M_1$is as follows,

The NFA $M_2$is follows,

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