4
$\begingroup$

I'm learning for the exam and have problems with this task:

Describe an algorithm that transforms a given NFA $A = (Q, \Sigma, \delta, q_0, F)$ (which may have $\epsilon$-transitions) into an equivalent NFA without $\epsilon$-transitions with the same condition number. And then determine the maturity of the algorithm. The algorithm should have a running time $O(|Q| · |\delta|)$ where $$|\delta| := \sum_{\substack{q\in Q\\ a\in\Sigma\cup\{\epsilon\}}} |\delta(q,a)|$$

$\endgroup$
  • 5
    $\begingroup$ What does “condition number” mean? What does “maturity of the algorithm” mean? These are bad translations, and I don't know what the right concept is. $\endgroup$ – Gilles 'SO- stop being evil' May 21 '12 at 23:36
  • 1
    $\begingroup$ What have you tried? What techniques have did you learn in your lessons, that may be applicable here? Where are you stuck? $\endgroup$ – Gilles 'SO- stop being evil' May 21 '12 at 23:37
  • 2
    $\begingroup$ condition->state; maturity->complexity (: looks like google-translate. $\endgroup$ – Ran G. May 22 '12 at 2:54
  • $\begingroup$ Exercise 5.1, due May 24th. $\endgroup$ – Raphael May 30 '12 at 8:05
2
$\begingroup$

The obvious answer is: the powerset construction gets rid of $\varepsilon$-transitions, so you can use it. It blows up the automaton exponentially in the worst case, though, so it is not directly applicable. However, you can use the part that deals with $\varepsilon$-transitions and keep nondeterminism.

That is, if a state $q$ has an $\varepsilon$-transition to $q'$, add all outgoing transitions of $q'$ to $q$ and remove the $\varepsilon$-transition. You have to iterate this process for every state because there may be chains of $\varepsilon$-transitions. In the worst case, you reach all transitions (for every state), causing the required runtime bound (to be sharp).

Note that formally, this does not change the number of states. It might lead to isolated states, though, that can safely be dropped.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ and why this algorithm has this runtime O(|Q|⋅|δ|) ? $\endgroup$ – user1619 May 23 '12 at 20:38
  • $\begingroup$ @sad: The argument is given in the spoiler area. What part do you not understand? Obviously, it is only a rough outline. Detailed analysis remains for you to do. $\endgroup$ – Raphael May 23 '12 at 20:58
  • $\begingroup$ has the algorithm the runtime of O(|Q|⋅|δ|) because he visits all states and transitions or just in worst case ? $\endgroup$ – user1619 May 23 '12 at 21:24
  • $\begingroup$ @mikley: In the worst case, it visits all transistions for every state, so the actual runtime is at most that large (up to constant factors). This is very basic; please stop abusing answer for commenting. If this is a problem for you, please consider asking a new question. $\endgroup$ – Raphael May 23 '12 at 21:52

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.