# Converting from NFA to a regular expression.

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.

-
If I counted parentheses correctly, the regular expression doesn't seem to accept an empty string. –  JiminP Aug 23 '13 at 16:52

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

-
Nice exposition of the technique. –  Brian M. Scott Aug 23 '13 at 17:28
Good job. You got the same answer as I did and saved me the trouble of writing it up (not to mention that my answer wouldn't have been as clear as yours). Congrats. –  Rick Decker Aug 23 '13 at 17:40
Thanks! I attribute my success to my early decision to \def\a{\mathtt{a}}\def\b{\mathtt{b}}. –  MJD Aug 23 '13 at 17:40
Thank you very much guys really. Can anyone share me links to such methods of conversion. –  Evy Lino Aug 23 '13 at 17:42
The language $K^*L$ is always a solution to the equation $X = KX + L$, but it is the unique solution only if $1 \notin K$. If $1 \in K$, then all the languages of the form $K^*M$ where $M$ contains $L$ are also solutions. Fortunately, one can show that this situation never occurs when the algorithm nicely presented by MJD is used. –  J.-E. Pin Aug 25 '13 at 8:30

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.

-