Example of language that does not contain substring $11$

Question

Let $\Sigma=\{1,0\}$

I just thought of sample strings that can work, such as, $\epsilon, 1, 11, 10, 0, 01$, and came up with:

$$R=1^*(\epsilon+01^*)$$

Is this correct? And is this the correct way to do it? I don't particularly like these questions where they ask you $x$ is not a substring. How do we even do those?

Answer 1

The title of your question is misleading. I suppose you are interesting in the language of all words not containing $11$ as a substring. More generally, given a word $u$, the set of words containing $u$ as a substring is the language $$ L(u) = \Sigma^*u\Sigma^* $$ Therefore, the set of words not containing $u$ as a substring is the complement of $L(u)$. If you want a regular expression for this language, you can proceed as follows

1. First compute the minimal DFA of $L(u)$ (this automaton has $|u| + 1$ states).
2. Compute the minimal DFA of its complement (just swap the final states and the non final ones).
3. Compute a regular expression from the resulting DFA.

For your example, $u = 11$, the minimal automaton of $L(11)$ is

and the minimal automaton of its complement is

It is now easy to get a regular expression for the language accepted by this automaton: $(0 + 10)^*(\varepsilon + 1)$.

Answer 2

As the substring $11$ is forbidden, any $1$ must be followed by a $0$ or nothing. So a good candidate is

$$(0+10)^*(\epsilon+1)$$ a little more symmetrically written $$((\epsilon+1)0)^*(\epsilon+1).$$

There are many more ways to avoid $11$, such as with the trivial $0^*$.