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.