Cost in time of constructing and running an NFA vs DFA for a given regex

Problem Detail: 

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.

Asked By : kiliki

Answered By : kiliki

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3071