Converting from NFA to a regular expression.

Question

This is a NFA, I have been working to covert it to a regular expression. After I'am done, I arrive at an expression as follows

$$ \left(((a\cup b)a^*b) (ba^*b)^*a\right)^* \left(((a\cup b)a^*b) (ba^*b)^*\right) $$

Now, I really doubt if the answere is correct if anyone could help. I used the state removal method.

Answer 1

I am going to write $S_i$ for the set of strings that cause the machine to go from the start state into state $i$.

From the diagram of the machine, we have:

$$\begin{align} \def\a{\mathtt{a}}\def\b{\mathtt{b}} S_1 & = \epsilon + S_3\a \\ S_2 & = S_1(\a+\b) + S_2\a + S_3\b \\ S_3 & = S_2\b \end{align}$$

(This part is crucial, and if you don't find this obvious, and don't see where I got these equations, leave a comment so I can explain it.)

After this it is all mechanical. Substituting $S_3$ into the equations for $S_1$ and $S_2$ gives:

$$\begin{align} S_1 & = \epsilon + \color{blue}{S_2\b}\a \\ S_2 & = S_1(\a+\b) + S_2\a + \color{blue}{S_2\b}\b \\ & = \color{darkred}{S_1(\a+\b) + S_2(\a + \b\b)} \\ S_3 & = S_2\b \end{align}$$

We can eliminate $S_2$ from its definition using the rule that says that if $X = p + Xq$ then $X = pq^*$:

$$\begin{align} S_1 & = \epsilon + S_2\b\a \\ S_2 & = S_1(\a+\b) + S_2(\a + \b\b) \\ & = \color{darkred}{S_1(\a+\b)(\a + \b\b)^*} \\ S_3 & = S_2\b \end{align}$$

Then we put the definition of $S_2$ into $S_1$ and apply the $X = p + Xq\implies X = pq^*$ transformation to it:

$$\begin{align} S_1 & = \epsilon + \color{blue}{S_1(\a+\b)(\a + \b\b)^*}\b\a \\ & = \color{darkred}{\left((\a+\b)(\a + \b\b)^*\b\a\right)^*}\\ S_2 & = S_1(\a+\b)(\a + \b\b)^* \\ S_3 & = S_2\b \end{align}$$

Now we have an explicit formula for $S_1$ (which it's not hard to see is correct), we could substitute this into the equations for $S_2$ and $S_3$ to get explicit formulas for the strings accepted in those states, but what we really want is to know the strings accepted by the entire automaton, which is exactly $$\begin{align}S_1 + S_3 & = S_1 + S_2\b \\ & = S_1 + S_1(\a+\b)(\a + \b\b)^*\b \\ & = S_1(\epsilon + (\a+\b)(\a + \b\b)^*\b)\end{align}$$

and since $S_1 = \left((\a+\b)(\a + \b\b)^*\b\a\right)^*$, then answer is that the automaton accepts

$$\left((\a+\b)(\a + \b\b)^*\b\a\right)^* (\epsilon + (\a+\b)(\a + \b\b)^*\b). $$

That first term, $\left((\a+\b)(\a + \b\b)^*\b\a\right)$, will always take the machine from the start state around the loop and back to the start state; after doing that some number of times, the machine can accept immediately (that's the $\epsilon$) or can proceed to state 3 via $(\a+\b)(\a + \b\b)^*\b)$.

Answer 2

MJD’s excellent answer illustrates a general technique for solving this sort of problem, but I think that it’s also worth pointing out what’s wrong with the regular expression that you got. The expression

$$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*a\Big)^*\tag{1}$$

captures every word that gets accepted at state $1$, and the expression

$$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*\Big)$$

captures everything that gets accepted at state $3$ without revisiting state $1$, so

$$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*a\Big)^*\Big(\big((a\cup b)a^*b\big)(ba^*b)^*\Big)\tag{2}$$

captures everything that gets accepted at state $3$. The union of $(1)$ and $(2)$ gives you what you want, and then an obvious application of distributivity lets you simplify it to

$$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*a\Big)^*\Big(\epsilon\cup\big((a\cup b)a^*b\big)(ba^*b)^*\Big)\;.$$

Thus, you actually had all of the major pieces; you just didn’t put them together quite right.