Converting NFA to DFA and then to regular expression.

Question

Convert the NFA into a DFA and then into a regular expression defining the language accepted by this NFA.

NFA

So far I have converted to a DFA (I hope) but do not know how I can convert to a regular expression.

DFA

I think the regular expression may be aU(bb)* but that is just from looking at the diagram.

Answer 1

The DFA looks fine, but the regular expression isn’t right. The automaton certainly accepts $(bb)^*$, but it also accepts $(bb)^*a(a\cup b)^*$: it can bounce back and forth between states $1$ and $2$ any number of times before reading an $a$, going to state $3$, and staying there no matter what else it reads. You can write this as $(bb)^*\cup(bb)^*a(a\cup b)^*$, or you can factor out $(bb)^*$ and write it as

$$(bb)^*\big(\epsilon\cup a(a\cup b)^*\big)\;,$$

where $\epsilon$ is the empty word. (Substitute $\lambda$ for $\epsilon$ if you use that for the empty word.) There is a mechanical procedure for converting a DFA to a regular expression, but this DFA is simple enough that it’s much easier to write down the regular expression by inspection.

Answer 2

A perhaps contrarian solution is to convert the NFA to an RE directly, and then convert the RE to a DFA using derivatives. For state $i$, let $L_i$ denote the language of words starting with $i$ and ending at an accept state. The NFA gives the following system of "linear equations" in the $L_i$'s: $$\begin{eqnarray} L_1&=&aL_1+(a+b)L_2 + \epsilon\\ L_2&=&bL_1 \end{eqnarray}$$ where $\epsilon$ is the empty word, $+$ denotes union. The key fact which makes such systems easy to solve is that, if $A$ and $B$ are languages, the unique language $X$ such that $X=AX+B$ is given by $X=A^*B$. Substituting the second equation into the first gives $$L_1=aL_1+(a+b)bL_1+\epsilon=(a+ab+bb)L_1+\epsilon;$$ the key fact gives $L_1=(a+ab+bb)^*\epsilon=(a+ab+bb)^*$.

To build a DFA using derivatives, we'll have states labeled with REs (as above, the RE matches words which start at that state and end at an accept state). For each RE $r$ and each symbol $s$, we have an edge $r\stackrel{s}{\rightarrow}\partial_s r$, where $\partial_s r$ matches words $w$ such that $sw$ matches $r$. So let $r=(a+ab+bb)^*$; we have $\partial_a r = (\epsilon+b)r=b?r$ and $\partial_b r = b r$. These are both new states; we have $\partial_a br=\phi$ and $\partial_b br=r$, where $\phi$ is the null regex which matches nothing. Similarly $\partial_a b?r=\partial_a r=b?r$, and $\partial_b b?r=r+br=b?r$. So our DFA has four states, labeled $r$, $br$, $b?r$ and $\phi$; the transition table looks like this:

$$\begin{array}{c|cc} &a&b\\ \hline r & b?r & br\\ b r & \phi & r\\ b?r & b?r & b?r\\ \phi & \phi & \phi \end{array}$$ The initial state is the one labeled $r$; the accept states are those whose regex matches the empty word, i.e. $r$ and $b?r$.