Regular expression for language that does not accept x string (3 letters, |x|=3) The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not contain "$ca$" at the end nor "$cab$" anywhere$\}$, $X_2=$"$bac$" and $X_3=\{w∈\{a,b,c\}^*| w$ does not contain "$ab$" at the start nor "$cab$" anywhere$\}$. What I find difficult to express is that "$cab$" does not appear anywhere in $X_1, X_3$ (the situation for "ca" and "ab" is simple because they consist only of 2 letters, we can split $X_1, X_3$ so that the "cab" problem remains). I have tried creating a NFA for this purpose but the automata needs to have quite a few loops (thus it is hard to find the regular expression). My question is whether there is a clever way to find the representation of non-existance of "cab", other than counting all the possibilities in the NFA that accepts such strings. If there is no such way, how can I find the regular expression of L from the start?
You can create a complete DFA (with all transitions populated) and then just invert the set of start and end states. In your case, using grammar notation, this accepts all strings with the sequence $cab$:

$$\begin{align*}
S &amp; \rightarrow Q_0 \\
Q_0 &amp; \rightarrow a Q_0\,|\,b Q_0\,|\,c Q_1\\
Q_1 &amp; \rightarrow a Q_2\,|\,b Q_0\,|\,c Q_1\\
Q_2 &amp; \rightarrow a Q_0\,|\,b Q_3\,|\,c Q_1\\
Q_3 &amp; \rightarrow a Q_3\,|\,b Q_3\,|\,c Q_3\,|\,\epsilon
\end{align*}$$

So this accepts all strings without the sequence $cab$:

$$\begin{align*}
S &amp; \rightarrow Q_0 \\
Q_0 &amp; \rightarrow a Q_0\,|\,b Q_0\,|\,c Q_1\,|\,\epsilon\\
Q_1 &amp; \rightarrow a Q_2\,|\,b Q_0\,|\,c Q_1\,|\,\epsilon\\
Q_2 &amp; \rightarrow a Q_0\,|\,b Q_3\,|\,c Q_1\,|\,\epsilon\\
Q_3 &amp; \rightarrow a Q_3\,|\,b Q_3\,|\,c Q_3
\end{align*}$$

Now you just have to convert that into a regular expression. Whether or not that's easier is up to you.

You can also directly construct a DFA which accepts $(a|b|c)^*bac(a|b|c)^* \setminus (a|b|c)^*cab(a|b|c)^*$ using Brzozowski's method, but that's a bit tricky to do by hand for this example.