# A little help with regular expressions [duplicate]

I am trying to create a regular expression that will generate the following language under the {a,b,c} alphabet: all words that do not contain the substring "bbc"

I am having a really hard time understanding how to approach this question. I have done several other questions where a certain substring must be excluded, but this one really messes with my logic.

## marked as duplicate by D.W.♦, J.-E. Pin, David Richerby, Luke Mathieson, JuhoNov 8 '13 at 23:00

• Design a NFA for $\{a,b,c\}^*bbc\{a,b,c\}^*$, make a DFA out of it, complement, read the expression from the automaton. This is in most cases the best way to solve this type of "pattern matching" problem. See other examples here. – Hendrik Jan Nov 5 '13 at 23:57
1. Negation isn't easy to express. There are no shortcuts. The resulting expressions may be far more complex than the expression you would get if negation was a basic operator in the expression language - in which case you could write $\neg(.^*bbc.^*)$, where $.$ is a shortcut for $(a\cup\neg a)$
2. Lacking $\neg$, the only way to say $\neg a$ for some symbol $a$ is to enumerate all other symbols: $\neg a = (b\cup c \cup d \cup \ldots)$. In Unix-like regular expressions, you can of course use [^a].
3. In compound expressions, you can use left factorization. E.g. $\neg(bbc) = \epsilon \cup \neg b\neg(bc) = \epsilon \cup \neg b(\epsilon \cup \neg c) = \ldots$. The key insight is that this can be made to work with Kleene star expressions, too; I suggest you invent or look up the details yourself.