Regular Expressions quiz



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

BD
BABD
BAADBAABDBAD
BAADBAABBDBAD

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

ABBBBB
ABBBCCBBBB
ACBB
AABBBCCBBBB

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)?

{2, 3, 4, 5, 7, 8, 9, 10}
{2, 3, 4, 5, 6, 7, 8, 9, 10}
{3, 4}
{3, 4, 5, 7, 8}

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?

M + N
MN
MN2
exponential in N