Michael Sipser Edition 3 Exercise 1 Question 8 (Page No. 84)

Question

Use the construction in the proof of $\text{Theorem 1.45}$ to give the state diagrams of $\text{NFA’s}$ recognizing the union of the languages described in

1. $L_{1}=\text{\{w| w begins with a 1 and ends with a 0\}}\cup L_{2}=\text{\{w| w contains at least three 1s\}}$
2. $L_{1}=\text{\{w| w contains the substring 0101 (i.e., w = x0101y for some x and y)\}}\cup L_{2}=\text{\{w| w doesn’t contain the substring 110\}}$ 

Comments

@Lakshman Patel RJIT

the actual question is

a. L1={w| w begins with a 1 and ends with a 0} union L2={w| w contains at least three 1s}

b. L1={w| w contains the substring 0101 (i.e., w = x0101y for some x and y)} union L2={w| w doesn’t contain the substring 110}

pls edit the question

---

@aditi19

Now i edit please check it.

---

👍 ok

Answer 1

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

b. L1={w| w contains the substring 0101 (i.e., w = x0101y for some x and y)} union L2={w| w doesn’t contain the substring 110}