According to the answers - the correct answer is C

I understand why there exists an NFA with O(a+b) states that accepts AUB

But I don't understand the second part - how do we not that there is no DFA with O(a+b) states that accepts AUB?

What if the minimal DFA that accepts A has alpha states

The minimal DFA that accepts B has beta states

but maybe a > alpha•beta , b > alpha•beta?

and then I can create a DFA M that accepts AUB according to what we saw in rec.01 and M has alpha•beta states = O(a+b)

Midterm exam - Spring 2006 Q2