6
$\begingroup$

Repost from Stack Overflow:

I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated.

The question I'm having problems with at the moment is as follows:

Given a regular expression (a|bb)*, derive an estimate of the cost in time for converting it to a corresponding NFA and a DFA. Your answer should refer to the size of the regular expression.

A similar question from another year is:

Given that, for the above example, you know the size of the original regular expression, |r| and the size of the input string |x|, explain how you would calculate the cost in time for constructing and running the NFA versus constructing and running an equivalent DFA.

The resulting NFA for (a|bb)* has 9 states, while the DFA has 4. Even knowing this, I have no idea how to approach the question.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

Kiliki's answer has some things wrong.

They say:

The construction time for an NFA should be O(m), where m is the number of nodes (don't quote me on that one, it's more of a semi-logical assumption than anything)

This doesn't even really make sense. If you are constructing a NFA from a regular expression there are no well defined "nodes" to speak of. A sufficient algorithm is the Thompson's construction.

Amortized time for constructing an NFA from a regular expression

A regular expression is composed literal characters stuck together in various ways

  • concatenation
  • alteration and
  • Kleene star.

Thompson's construction defines rules for making an NFA for literal characters. For the character 'x' where Os are states. 

       x
    O ---> O

There are other rules for concatenation, etc. that join together NFA's like the one above, but the important part is that any operation adds a small finite number of states and transitions (never more than two states or four transitions actually. If you want the details have a look at the super helpful wiki link above).

The number of literals and operations (concatenation, etc.) is easily determined from the length of the string of the regular expression. The amount of one or the other is different only by a constant factor. Thus we can safely say that constructing an NFA from a regular expression using Thompson's construction is O(n) where n is the length of the string of the regular expression.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It's somewhat unusual to define the running time of an algorithm in terms of its output rather than its input, but it seems to make sense. $\endgroup$
    – David Richerby
    Commented May 10, 2017 at 19:31
  • $\begingroup$ @DavidRicherby How does this make sense? The only way I can parse it is as a sort of tautology --- "This algorithm takes as long as it takes to make its output using this algorithm" --- and this isn't helpful information. $\endgroup$
    – leafmeal
    Commented May 10, 2017 at 23:50
  • $\begingroup$ There's no tautology because you're describing the time taken to produce the output in terms of the output's length. This doesn't always make sense (e.g., for any decision problem, the output is a single bit, but the running time depends on the input) but sometimes it does. One context is in enumeration algorithms where you might need to produce a list which is necessarily exponentially long in the size of the input; the running time is often measured in terms of the output. $\endgroup$
    – David Richerby
    Commented May 11, 2017 at 6:31
1
$\begingroup$

Preface: I asked this question yesterday, so don't assume I know what I'm talking about. This should get you on the right path (I hope), but don't take it as fact.

Remember to read the comments below. Much of the original answer is incorrect, but the tips from helpful and more experienced people below should help clear it up.

From my understanding of it, the cost in time (or memory) is based on orders of complexity. As per: http://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times

  • The construction time for a DFA from an NFA is O(2^m) where m is the number of nodes.
  • The running time of a DFA is O(n) where n is the length of the input string. This is because there is only 1 path through the DFA for a given string.
  • The construction time for an NFA should be O(m), where m is the number of nodes (don't quote me on that one, it's more of a semi-logical assumption than anything)
  • The running time for an NFA is O(m²n) because it is non-deterministic and the computer must check every possible path for the current character in the string. (assuming no lookahead, it doesn't know what the next character will be so it runs into dead ends)

So for an NFA with 9 nodes (m) and an input string of length 4 (n):

  • The construction time for the DFA is O(2^m) while the construction time for the NFA should simply be O(m). These equate to 512 and 9 respectively.

  • The running time for the DFA is O(n) while the running time for the NFA is O(m²n) these equate to 4 and 1296.

For the sake of argument, we'll assume each operation takes 1 'tick' (could be operations, milliseconds, etc). If we convert to a DFA we're looking at 516 'ticks' to construct the DFA and check the string. If we run the NFA we end up with 1300 'ticks'. Without being given a running time for an operation or the clock speed of the processor, these are simply relative numbers and should be compared in relative terms.

As to questions that may ask whether it is 'worth converting' (sounds like a terrible question but hey), the answer is yes in most cases due to the fact that once constructed the DFA would be used to check multiple strings of varying length, making the construction time less relevant than the running time.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ Note that the "runtimes" you found are a) upper bounds on b) the worst case but c) only up to a constant factor. So the numbers you have computed are utterly meaningless. I suggest you execute the algorithms on your examples (they are small, so that's possible) and count. $\endgroup$
    – Raphael
    Commented Aug 8, 2012 at 20:34
  • 1
    $\begingroup$ The running time for an NFA should be $O(m^n)$, because for each of the $n$ characters in the input string, you have up to $m$ choices for the next state. You have to try every possible path for the entire string, not just for each character. $\endgroup$
    – JeffE
    Commented Aug 8, 2012 at 21:39
  • $\begingroup$ thanks for the tips, if either of you wants to/can edit the answer go ahead. At the moment it's pretty much my flawed view as someone trying to pick it up just before an exam. $\endgroup$
    – kiliki
    Commented Aug 8, 2012 at 22:46
  • $\begingroup$ @Raphael by executing the algorithms on the examples do you mean I should build and simulate running the dfa/nfa? can't seem to get my head around integrating those ideas with an example otherwise and that seems a bit of an exhaustive method for a single question in a paper. $\endgroup$
    – kiliki
    Commented Aug 8, 2012 at 23:41
  • 1
    $\begingroup$ @JeffE: I have great respect for you, but your comment above is really completely totally wrong. See courses.engr.illinois.edu/cs373/Lectures/lec05.pdf for how you can deterministically simulate running an $m$ state NFA on an input of length $n$ in time $O(m^2 n)$ (without first constructing the DFA from the NFA.) $\endgroup$
    – Wandering Logic
    Commented May 11, 2013 at 16:48

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.