The regular expression representing all binary strings where no occurrence of 00 is immediately followed by a 1

regular expressionsregular-language

I am currently working on constructing regular expressions that match a description of a given set of strings from practice problems in my textbook (no solutions are provided in it). I am trying to construct a regular expression for all binary strings where no occurrence of $00$ is immediately followed by a $1$.

My attempted solution: $(1\cup 01)^*(000^* \cup \epsilon)$

However, I think my solution is incorrect. I think it's due to the fact that it doesn't accept the string $0$ even though it should. I'm unsure on how to resolve this issue in my solution. I tend to struggle when it comes to constructing regular expressions and strings. Any feedback or suggestion would be appreciated.

Best Answer

I think you are quite close. Although it is hard to accurately guess your intent from just a single expression, it looks like you are trying to capture the idea that once the string contains any $00$, it’s forced to contain only zeros from that point on. A simpler way to express that is just to end your expression with $0^*$ rather than $(000^* \cup \epsilon)$: adding any number of zeroes to the end of a valid string will not make it invalid.

This has the side effect of addressing your issue that the expression doesn’t represent $0$. But is that enough? The left half is responsible for encoding all strings that contain at most one consecutive zero, and do not end in zero. And that is indeed what it does: it allows for an empty string, but if it starts with a $0$ that must be immediately followed by a $1$, while if it starts with a $1$ then any valid string can follow. So with that small adjustment, your expression works.

It’s natural to find it harder to express arbitrarily regular languages as regular expressions rather than an automaton. For instance, even though regular languages are closed under complements, it is usually quite painful to negate the logic of a regexp, while negating a DFA is super easy.

One thing worth keeping in mind is that you could always express a language as a DFA and then apply the standard method for converting DFAs to a regular expression.

Related Question