A regular expression for all strings over ${1, 0}$ which do not have $111$ as a substring

Question

Would the following be a correct regular expression for this?:

$$(0 + 01 + 011)^* + (0 + 10 + 110)^* + (1 \cdot (0 + 01 + 011)^*) + ((0 + 10 + 110)^* \cdot 1) + 11 + 1$$

My thought process is I broke it into 4 cases (in addition to the $1$ and $11$ cases):

• First case: all strings that start with 0 but end in 1
• Second case: all strings that with 0 and end in 0
• Third case: all strings that start with 1 and end in 1
• Fourth case: all strings that start with 0 but end in 1

Is this correct?

Answer 1

Looks good to me, but it might be a bit redundant. For me, it would be easier to draw a DFA:

then use the standard algorithm for converting a DFA to a regex. This yields something like: $$ (0 + 10 + 110)^*(\varepsilon + 1 + 11) $$

Answer 2

If you concentrate on the blocks of 1s, you can see that the have to come in clumps of one or two, each clump separated by at least one 0, which suggests:

• zero or more 0s, followed by
• as many repetitions as you want of
• • one or two 1s, followed by at least one 0.