3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.