Which of the following strings is not matched by the regular expression (B(AB|A)∗D)∗

Consider the NFA below. What one of the following strings is not accepted by the NFA?

Consider the NFA below for the regular expression (A(B*|C)*). What is the set of all states that the NFA could be in after reading in ABBB (and following any epsilon transitions)?

What is the order of growth of the worst-case running time of the Java function call input.matches(re) as a function of the length N of the input text and the length M of the regular expression pattern?