I'm working through a textbook on automata theory (Introduction to Automata Theory, Languages, and Computation) and I'm stuck on the Exercise 3.1.3:
Write regular expressions for the following languages:
a) The set of all strings of 0's and 1's not containing 101 as a substring
I can't think of a way to directly construct regular expressions, so I created a DFA:
thus I can convert it to a regular expression.
My result is $$0^*+0^*1(000^*1+1)^*+0^*11^*0(00^*11^*0)^*+0^*11^*00(0+11^*00)^*$$However the answer I found online is $$0^*(1^*000^*)^*1^*0^*$$So I tried to simplify my result and found I couldn't, does my results go wrong, or could you help me simplify it?
In Regex it would be ^0*(1+(00+)?)*(10)?$
EDIT: Also, a useful resource for debugging Regex: https://regex101.com/