Regular Expression to a Deterministic Finite Automata with Kleene Closure

Question

I'm asked to make a DFA for the following:

$\Sigma = \{a, b \} $ and $\{ $ w | w does not contain the string ab $ \}$.

My first approach was to convert this into a regular expression by taking the complement of what they're asking (seemed easier to do). Which yields: (a+b)*ab(a+b)* : a string that contains ab.

The issue I'm having with this is the (a+b)* and converting into a DFA. Unlike an NFA, a DFA does not have any $\lambda $ transitions, which makes it difficult to separate states. How can a state "return" to a previous state in order to fulfill the possibility of a Kleene closure for the above regular expressions: e.g. an a or b, zero or more times.

Unfortunately I'm not sure how to draw a state machine here and not quite sure if this is the place to ask automata related questions and computer science.

Answer 1

The most direct approach is the one suggested by amd in the comments: the language in question corresponds to the regular expression $b^*a^*$, since if you once get an $a$, you cannot ever again get a $b$.

None the less, your first approach will work, but instead of working from $(a+b)^*ab(a+b)^*$, design the machine directly. If $q_0$ is the initial state, you want to stay there as long as you keep reading $b$, so you want a transition $q_0\overset{b}\longrightarrow q_0$. When you read an $a$, there’s a chance that it’s the beginning of an $ab$ sequence, so you want to go to a different state: $q_0\overset{a}\longrightarrow q_1$. If you’re in $q_1$ and get another $a$, you want to stay at $q_1$: that $a$ could be immediately followed by a $b$. If, on the other hand, you get a $b$, you need to head off to an acceptor state. Thus, you want transitions $q_1\overset{a}\longrightarrow q_1$ and $q_1\overset{b}\longrightarrow q_2$, where $q_2$ is an acceptor state. Once you get to $q_2$, the word is to be accepted no matter what the rest of the input is, so both inputs will just keep you at $q_2$: $q_2\overset{a,b}\longrightarrow q_2$. The final step, of course, is to change acceptor to non-acceptor states and vice versa.

If you want to think of this in terms of regular expressions, it amounts to recognizing that $(a+b)^*ab(a+b)^*$ can be rewritten as $b^*a^*ab(a+b)^*$.

Answer 2

Loosely speaking, a DFA will have a state for each fact that it needs to “remember” about its input. This may require adding nodes to sort out what’s going on in NFA $\lambda$-transitions. Returning to a previous state isn’t a big deal: a transition can take you to a “previous” state. The old KMP string search algorithm, which is really a DFA in disguise illustrates this sort of thing. A good starting point for understanding how a DFA handles NFA $\lambda$-transitions is any of the algorithms for converting a NFA to a DFA. Any good reference on finite-state automata should have one, as it’s a common way to prove their equivalence.

Neither the language that you’re trying to encode nor its complement requires any backtracking, though. The machines are pretty small, so I’ll represent them with transition tables. Accepting states are marked with an asterisk.

The language $\mathbf{b^*a^*}$ is accepted by the following DFA: $$ \begin{matrix} & \mathbf a & \mathbf b \\ \hline S^* & 1 & S \\ 1^* & 1 & 2 \\ 2 & 2 & 2 \end{matrix} $$ It loops in the start state until it consumes an $\mathbf a$, at which point it transitions to the “I’ve just seen an $\mathbf a$” state that loops on $\mathbf a$’s and accepts if it ends there. If it consumes a $\mathbf b$ while in this state, it transitions to a non-accepting state that consumes the rest of the string.

The complement $\mathbf {\Sigma^*ab\Sigma^*}$ is accepted by this machine: $$ \begin{matrix} & \mathbf a & \mathbf b \\ \hline S & 1 & S \\ 1 & 1 & 2 \\ 2^* & 2 & 2 \end{matrix} $$ which is simply the previous machine with accepting and rejecting states swapped. Note that there’s not a separate state that corresponds to the $\mathbf a$ in the leading $\mathbf{\Sigma^*}$ (it’s gotten merged into the “I’ve just seen an $\mathbf a$ state), nor is there a separate state for the trailing $\mathbf{\Sigma^*}$. This will often be the case.