Question

Use the construction in the proof of Theorem 1.49 to give the state diagrams of NFAs recognizing the star of the languages described in

a. Exercise 1.6b

b. Exercise 1.6 j

c. Exercise 1.6m

THEOREM1.49

The class of regular languages is closed under the star operation.

Short answer

a.

b.

c.

Step-by-step solution

Explain the given information

Given that Theorem 1.49 , states that the class of regular languages are closed under star operation.

(a) Give the state diagram of NFA recognizing the star of the language

Consider the language $L_1=\left\{w|w\text{containsminimumthree}1\text{'}s\right\}$. Let $M_1$be the NFA that recognizes localid="1663238901072" $L_1$.

Consider that, localid="1663238860678" $L=L{*}_1$, let localid="1663238872432" $M$be the NFA that recognizes localid="1663238885929" $L$.

localid="1663238918361" $L_1=\left(0.1\right)*1\left(0.1\right)*1\left(0.1\right)*1\left(0.1\right)*$

The NFA localid="1663238930433" $M_1$that recognizes the language localid="1663238941815" $L_1$is as follows,

Therefore, the state diagram localid="1663239665261" $M$that recognizes localid="1663239651469" $L$is as follows.

(b) Give the state diagram of NFA recognizing the star of the language

Consider the language $L_1=\left\{w|w\text{includesminimumtwo}0\text{s}\text{andmostlyone}1\text{s}\right\}$.

Let $M_1$ be the NFA that recognizes the language $L_1$.

Let $L=L{*}_1$, and $M$be the NFA that recognizes $L$.

The state diagram of $M_1$is as follows,

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

(c) Give the state diagram of NFA recognizing the star of the language

The language describes the empty string.

The state diagram of NFA that recognizes the empty string is as follows,