I'm working through a textbook on automata theory and I'm stuck on this regular expression problem.
Create a regular expression for the following language:
The set of all strings that do not contain "101" as a substring.
I tried to create the expression and found I couldn't, so I create an automata, but I have figured out how to translate it into a regular expression.
Best Answer
One way is to take it in pieces. Clearly your automaton accepts $0^*$. What else gets it back to state $a$? Only $11^*00$, after which you can have any number of zeroes again. Thus, $0^*(11^*000^*)^*$ almost does the trick. However, like your automaton, it misses the possibility that an acceptable string can end in $1$ or $10$ if no $0$ immediately precedes the $1$. (For example, the words $11$ and $1110$ should be accepted.) Can you see how to adjust it (and your automaton) to reflect that possibility?