Arden's Rule, DFA & NFA to regular expressions

Question

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.

Answer 1

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