Show that the language is regular without a DFA

Question

How can I show that the language {$w \epsilon$ {$0,1$}$^{*}:$ the word $w$ contains neither the (sub)string $000$ nor $11$} is regular without using a DFA? (Using the closure properties)

Answer 1

Let $L$ be the language in question. Here are four possibilities:

1. Come up with a regular expression that generates $L$.
2. Come up with a regular grammar that generates $L$.
3. Show that $L$ satisfies the condition of the Myhill-Nerode theorem.
4. Show that $L$ is the complement of a regular language over $\{0,1\}$.

The first two are self-explanatory, I think, though not necessarily easy. The third is actually fairly straightforward if you’ve seen the Myhill-Nerode theorem: words in that contain $000$ or $11$ are in one equivalence class, and the other classes can be identified by looking at the last one or two symbols of the word. The fourth is also straightforward, since it’s not hard to write a regular expression or grammar for the complement of $L$.