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

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.