3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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"

$\endgroup$
1
  • 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$ – Bram Fran Nov 3 '19 at 9:54
0
$\begingroup$

This would be the DFA for this problem:

DFA

Then we can create the Regular Expression from the DFA above:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.