Styjun

I need to transform this finite automata to regular expressions via converting the DFA (Deterministic Finite Automata) to a general NFA (Non-deterministic Finite Automata). How one should go about it? Will state diagrams of the NFA and the DFA will be identical?

So there are two DFAs in the picture, so I'll show how to get the RE for each one in turn. For the first, we write down some equations:

(q1) = (q1)a + (q2)b + e
(q2) = (q1)b + (q2)a

Now we can use the rule (q) = (q)x + y <=> (q) = yx* on each:

(q1) = ((q2)b + e)a*
(q2) = (q1)ba*

Now we can substitute in and since we care about (q2) we might as well get that directly:

(q2) = ((q2)b + e)a*ba*
 = (q2)ba*ba* + a*ba*
 = a*ba*(ba*ba*)*

We get the regular expression a*ba*(ba*ba*)* which, at a glance, appears to be correct. How did we get the equations? For each state, we wrote down the ways of "getting to" the state, and combined them with + (or, union). We include the empty string e in (q1)'s equation since (q1) is the initial state and nothing needs to be consumed to get there (initially).

For the second, the equations look like this:

(q1) = (q3)a + e
(q2) = (q1)(a + b) + (q2)a + (q3)b
(q3) = (q2)b

We can use our rule to eliminate the self-reference for (q2):

(q1) = (q3)a + e
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = (q2)b

Now we substitute and use the rule again:

(q1) = (q3)a + e
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = ((q1)(a + b) + (q3)b)a*b
 = (q1)(a + b)a*b + (q3)ba*b
 = (q1)(a + b)a*b(ba*b)*

Now we substitute again and use the rule again:

(q1) = (q1)(a + b)a*b(ba*b)*a + e
 = e((a + b)a*b(ba*b)*a)*
 = ((a + b)a*b(ba*b)*a)*
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = (q1)(a + b)a*b(ba*b)*

We can now substitute back in to get the expression for (q3):

(q1) = ((a + b)a*b(ba*b)*a)*
(q2) = ((q1)(a + b) + (q3)b)a*
(q3) = ((a + b)a*b(ba*b)*a)*(a + b)a*b(ba*b)*

The regular expression will be the union of the expressions for (q1) and (q3) since these are the accepting states:

r = ((a + b)a*b(ba*b)*a)* + ((a + b)a*b(ba*b)*a)*(a + b)a*b(ba*b)*
 = ((a + b)a*b(ba*b)*a)*(e + (a + b)a*b(ba*b)*)

The first part of this takes you from the state q1 back to the state q1 in every possible way; the second part says you can stay in q1 or do the other thing, which leads to q3, otherwise.

Wikipedia references this course PDF: Second Part of Regular Expressions Equivalence with Finite Automata, and according to this document, the procedure starts with this initial step:

A DFA is converted to a GNFA of special form by the following procedure:

1. Add a new start state with an epsilon arrow to the old start state and a new accept state with an epsilon arrow from all old accept states.

(emphasis mine)

So the NFA and DFA will not be identical. This also explains how to deal with multiple accepting states.

NO the state diagrams of the NFA and the DFA will not be identical during the conversion process.

For the second FSM regex will be -
ε U (aUb) ab (bUa(aUb)ab)* (εUa)

You can refer to these steps -

Here's an example -
These are screenshots from the PDF version of the book - "Introduction to the theory of computation" by Michael Sipser.