principleMinor
Cost in time of constructing and running an NFA vs DFA for a given regex
Viewed 0 times
dfanfaregextimeconstructingrunningforandcostgiven
Problem
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.
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.
Solution
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
Thompson's construction defines rules for making an NFA for literal characters. For the character 'x' where
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.
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 ---> OThere 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.
Code Snippets
x
O ---> OContext
StackExchange Computer Science Q#3071, answer score: 2
Revisions (0)
No revisions yet.