# How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent

Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form:

To a regular expression equivalent. What I have tried was using arden's rule. However I just cant figure out how to simplify and return the appropriate regular expression corresponding to that NFA.

First I have created the initial equation corresponding to those states:

$1: q3 = q_1 0 + q_1 1$

$2: q1 = q_0 0 + q_1 1$

$3: q0 = q_0 0 + q_0 1 + \epsilon$

Which I have tried to simplify:

$1: q3 = (q_0 0 + q_1 1)0 + (q_0 0 + q_1)1$

$1: q3 = q_0 00 + q_1 100 + q_0 01 + q_1 11$

$1: q3 = q_0(0+1) + q_1(0+1)$

$2: q1 = q_0 00 + q_0 10 + \epsilon 0 + q_0 01 + q_1 11$

$2: q1 = q_0(0+0+1)+ \epsilon 0 + q_1 11$

$3: q0 = q_0 0 + q_0 1 + \epsilon$

$3: q0 = q_0(0+1) + \epsilon$

Here I just lost. Maybe there is a different approach suitable in this context.

Appreciate any help!

• Did you draw the transition table and try subset construction ? – user93 Jan 22 '18 at 5:21
• Hi yes, I think your example is not correct since if you convert that NFA to DFA it will have multiple final states. – Googme Jan 22 '18 at 5:42
• I used your nfa diagram to draw the transition table and use subset construction to get the dfa. nfa to dfa does not always need to have multiple final states – user93 Jan 22 '18 at 5:49
• Nevertheless, it does not illustrate how to approach the problem I have. – Googme Jan 22 '18 at 6:11
• The video provided in the link explains it in details – user93 Jan 22 '18 at 6:34

The Arden's rule, as it is usually stated, is easier to use if you consider equations on $(L_q)_{q\in Q}$ depicting the language $L_q$ the automaton accepts from state $q$. Doing this, you obtain the following equations. Check that you understand this properly :

• $L_0 = 0L_0 + 1L_0 + 0L_1$
• $L_1 = 0L_3 + 1L_3$
• $L_3 = \varepsilon$

(I use $L$ instead of $q$ as it looks less misleading to me)

Once you have those equations, you can solve this as follows

• $L_1 = 0 + 1$ (I replaced $L_3$ with its value)
• $L_0 = (0+1)L_0 + 0(0+1)$ (Replaced $L_1$ and factorized. This is ready for Arden's rule)
• Since $\epsilon\not\in L_0$, from Arden's rule : $L_0 = (0+1)^*0(0+1)$

The language accepted by the automaton is always the union of the $L_{q_i}$, where the $q_i$ are the initial states. So here, $L = L_0 = (0+1)^*0(0+1)$

• Hi wazdra, is there a way you could show me how to solve them since thats where Im struggling at – Googme Jan 22 '18 at 7:38
• Did you understand how I got the equations ? I solve them right underneath. If you are talking about your equations, those are really not suited for Arden's rule – wazdra Jan 22 '18 at 7:41
• Hmm Im not 100% sure, you are saying that the regular expression corresponding to that NFA in my example is (0+1)*0(0+1)? – Googme Jan 22 '18 at 7:50
• Yes. Solving is easier than creating the equations at start. – wazdra Jan 22 '18 at 7:59
• Yes, $L_3$ corresponds to the language this automaton would accept if you started from $q_3$. Since $q_3$ is an accepting state, you would accept e. Since there is no transition out of $q_3$, this is all you can accept. So $L_3 = e$. – wazdra Jan 22 '18 at 8:20