Language of strings not containing 101

Question

Can someone show how we can systematically come up with regular expression for language not containing string 101 on alphabet {0,1} by first creating DFA and then converting it to regular expression?

Answer 1

• At first you make a DFA for this . After we can find regular expression .

 

Comments

From the third state can't we make a transition to the 2nd state on 0 without adding one extra state ?

---

well in DFA for accepting 101 we can make transition of 0 from 3rd state to 1st state...so we will need 4 states only...dnn need that extra stage

---

Yes sorry.. 1st state not 2nd..

---

@mini panda yes that can be done..!

---

well, I was also able to come up with the DFA, point was how do I reduce this DFA to regex. I have come up with following reduction of dfs to regex. Tell me if it looks correct:

---

answer is correct..!

---

Can you please explain the way to get regular expression from dfa?

Answer 2

(λ + 0)( 1+ 000* )(λ + 0)  +   0*1*0*

is this  a possible regular exprssion??

please correct me if not.

 

Answer 3

After getting this Just Do complement of it.