Drawing a DFA for a language/regular expression

Question

how would you draw a DFA for the language over {a,b,c} of all words where every occurrence of b is preceded and followed by a.

My thinking of this is that the regular expression for this is a* c* (aba)* a* c* although I am not too sure. Any help would be appreciated thanks

Answer 1

So, first, your regular expression

$$a^* c^* (aba)^* a^* c^*$$

is not correct. We need to give it the capacity to deal with many $aba$s, any of which can be surrounded by $a$s and $c$s. So, that would give us

$$(a^* c^* (aba)^* a^* c^*)^*$$

Of course, we still have a few more problems. First, we might have no $b$s, which could still fit into the language you've specified. We can fix that by pulling out the first set from our larger expression:

$$a^* c^* ((aba)^* a^* c^*)^*$$

We can't know the order of the $a$s and $c$s, so we need to use the union operator, which behaves essentially like an or in regexes:

$$(a\cup c)^* ((aba)^* (a\cup c)^*)^*$$

We're not done yet, as Thumbnail pointed out, we still need to allow $ababa$, so this gives us Thumbnail's structure, which allows any number of $baa^*$s after an $a$.

$$(a \cup c \cup a (b a a^*)^*)^*$$

Now, as for your DFA, begin with a start state, and let it accept the empty string:

Clearly, we can have as many $c$s as we want without changing our accept state:

$b$s are a little different, because they may be the start of an $aba$ pattern. This means that we need a new state to encode that we've encountered n $a$:

Now, if we arrive at a $c$, then our $a$ was not the start of an $aba$, and we can return home. If we get another $a$, then we may still be at the start of an $aba$ set:

Finally, we might exit with a $b$, followed by an $a$, which could be the beginning of a new set:

At this point, we are done. What we did not put in were the transitions to the garbage state, which are implicitly anything that wasn't yet defined. If we were to put them all in, we would have a graph that looks more like this:

Notice that one we get to state $g$, there is no way out, and no way to reach an accept state.

Answer 2

Amending @Choirbean's answer to accept $ababa$ and the like, a suitable regular expression is

$$(c \cup a (b a a^*)^*)^*$$

This is abbreviated from the previous ...

$$(a \cup c \cup a (b a a^*)^*)^*$$

... since the initial $a$ can be absorbed in the final $a (b a a^*)^*$.

We can now derive a compact set of right linear/regular equations:

$$\begin{align} Q_0 &= (c \cup a (b a a^*)^*)^*\\ Q_0/c &= Q_0 \\ Q_1 &= Q_0/a\\ &= (baa^*)^* Q_0 \\ Q_1/a &= Q_1 \\ Q_1/ba &= Q_1 \\ Q_1/c &= Q_0/c \\ &= Q_0 \end{align}$$

Where $\Sigma/\omega$ is those words $w$ for which $\omega w$ is in $\Sigma$.

• All the other transitions lead to $\varnothing$.
• The equations are equivalent to the DFA in @Choirbean's answer, though I've short-circuited the $ba$ transition through $Q_2$.