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

Improve this question
$\endgroup$
4
  • 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, 2012 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, 2012 at 23:37
  • 2
    $\begingroup$ condition->state; maturity->complexity (: looks like google-translate. $\endgroup$
    – Ran G.
    May 22, 2012 at 2:54
  • $\begingroup$ Exercise 5.1, due May 24th. $\endgroup$
    – Raphael
    May 30, 2012 at 8:05

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ and why this algorithm has this runtime O(|Q|⋅|δ|) ? $\endgroup$
    – user1619
    May 23, 2012 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, 2012 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, 2012 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, 2012 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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