1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You are close, but what happens if you want to generate the word $abacaba$? $\endgroup$ – Gray May 15 '17 at 19:21
  • $\begingroup$ Do you want a DFA or a regular expression? $\endgroup$ – Yuval Filmus May 15 '17 at 19:51
  • $\begingroup$ @YuvalFilmus I want a DFA, though I am using the idea of a regular expression to get an idea of what the DFA might look like. $\endgroup$ – Sujjan Shaikh May 15 '17 at 20:08
  • $\begingroup$ The words suggest that $ababa$ is allowed. Is this so? $\endgroup$ – Thumbnail May 16 '17 at 9:15
2
$\begingroup$

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:

start

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

start with c transition

$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$:

a state

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:

exiting a state

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

aba

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:

garbage state

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

$\endgroup$
  • $\begingroup$ I don't think the DFA is right, you seem to have provided what looks a "bab" pattern, but I think if you switch the b transitions with a transitions and vice versa, then it will be correct $\endgroup$ – Sujjan Shaikh May 15 '17 at 22:01
  • $\begingroup$ Ah, sorry about that - fixed! $\endgroup$ – Ben I. May 15 '17 at 22:42
  • $\begingroup$ As I read it, $ababa$ is allowed. Then $q_2 a$ ought to be $q_1$, not $q_0$. $\endgroup$ – Thumbnail May 16 '17 at 9:13
  • $\begingroup$ @Thumbnail ababa should be allowed in which case you are right. $\endgroup$ – Sujjan Shaikh May 16 '17 at 10:19
  • $\begingroup$ I've put a corresponding regular expression in a separate answer, since it doesn't format well in a comment. $\endgroup$ – Thumbnail May 16 '17 at 10:42
1
$\begingroup$

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$.
$\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.