Michael Sipser Edition 3 Exercise 1 Question 10 (Page No. 85)

Question

Use the construction in the proof of $\text{Theorem 1.49}$ to give the state diagrams of $NFA's$ recognizing the star of the languages described in

1. $\text{\{w| w contains at least three 1s\}}$
2. $\text{\{w| w contains at least two 0's and at most one 1\}}$
3. $\text{The empty set}$

Answer 1

a.L=(0*10*10*1(0+1)*)*

b. L=(000*+(100+010+000*1)0*)*

 

c. Ф*=ε