# Arden's Rule, DFA & NFA to regular expressions

I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state:

if x = s + xr
then x = sr*, with $$s,r\in$$ Regular Expressions

With that said, when I'm trying to transform one DFA in a RE this questions pop:

For example regarding this DFA

1. The $$\epsilon$$ is added in the entry stage A or in the final stage D and A ?

2. The equations should be written regarding the transitions in or out of a given state

2.1 For example A = $$\epsilon$$ + 0B + 1C or A = $$\epsilon$$ + 0C

3. Can the equational method and Arden's Rule be applied to a NFA with multiple initial states ?

Final thoughts, I have been trying out and it seems that when we count the transitions out of a state the $$\epsilon$$ should be added to the final state. When we count the transitions into a state the $$\epsilon$$ should be added to the initial state.

Keep in mind that I SERIOUSLY doubt my conclusions and I really need some help.

You can use either way. In both cases you construct a mapping from the states of the automaton to regular expressions, $$[-]: Q\to RE$$.

Let $$(s, l, t)$$ denote a transition from $$s$$ with label $$l$$ to target state $$t$$.

Also, let $$\oplus_{i\leq n}r_i = r_1 + \ldots + r_n$$.

## 1st case: By incoming edges.

1. Add a final state, $$F$$, and an $$\varepsilon$$-transition from each previous final state to $$F$$.
2. For every state $$X$$ with $$n$$ incoming edges $$(s_i, l_i, X)_{i\leq n}$$, make an equation $$[X] = \oplus_{i\leq n}([s_i]l_i)$$.
3. Use rule: $$X = s + Xr \Longrightarrow X = sr^*$$ on the equations
4. The final regular expression is $$[F]$$.

## 2nd case: By outgoing edges.

1. Add a new initial state, $$S$$, and an $$\varepsilon$$-transition from $$S$$ to the previous initial state.
2. For every state $$X$$ with $$n$$ outgoing edges $$(X, l_i, t_i)_{i\leq n}$$, make an equation $$[X] = \oplus_{i\leq n}(l_i[t_i])$$.
3. Use rule: $$X = s + rX \Longrightarrow X = r^*s$$ on the equations
4. The final regular expression is $$[S]$$.

Both methods work for NFAs as well. None of the above transformations depend on determinism.

Regarding your final thoughts, when you count the outgoing edges, if you add the $$\varepsilon$$-transition in the final states, then $$[F] = \emptyset$$, because $$F$$ (the new final state) has no outgoing edges, and this doesn't contribute to the equations. What you want to add is a new initial state, so that you can compute $$[S]$$. For your DFA example, $$[S] = \varepsilon[A]$$. Similarly, adding a new initial state is useless when transforming by incoming edges. In this case, $$[S] = \emptyset$$ and what you want is $$[F]$$, which for your example, would be $$[F] = [A]\varepsilon + [D]\varepsilon$$.