# 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?

## 3 Answers

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 & \rightarrow Q_0 \\ Q_0 & \rightarrow a Q_0\,|\,b Q_0\,|\,c Q_1\\ Q_1 & \rightarrow a Q_2\,|\,b Q_0\,|\,c Q_1\\ Q_2 & \rightarrow a Q_0\,|\,b Q_3\,|\,c Q_1\\ Q_3 & \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 & \rightarrow Q_0 \\ Q_0 & \rightarrow a Q_0\,|\,b Q_0\,|\,c Q_1\,|\,\epsilon\\ Q_1 & \rightarrow a Q_2\,|\,b Q_0\,|\,c Q_1\,|\,\epsilon\\ Q_2 & \rightarrow a Q_0\,|\,b Q_3\,|\,c Q_1\,|\,\epsilon\\ Q_3 & \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.

Try something like this:

(3 character stuff that is allowed many times)* (1 and 2 character stuff that is allowed once)(bac)(3 character stuff that is allowed many times)* (1 and 2 character stuff that is allowed once)

The 3 character stuff and 1/2 character stuff are there to forbid the sequence "cab"

• But how do you handle the fact that the left (3 characters)* could be any string that ends in c (aac, abc, acc, bac, bbc, bcc, cac, cbc, ccc) and the (1 or 2 characters) part the character a? "aac.a.bac", is not part of L, but "aac.b.bac" (using "aac" and not "a") and "cba.a.bac" (using a string that does not end in "c" but using "a" after that) are. – Bram Fran Nov 3 '19 at 9:54

This would be the DFA for this problem: Then we can create the Regular Expression from the DFA above:

$$([ab]^*(c[bc]|(ca)^+(a|c[bc]))^*)^*(ca|c)^*$$