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"
-
1$\begingroup$ 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. $\endgroup$ Nov 3, 2019 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)^*$
