HQS8 [2 pages, 5+5=10 points] Suppose you are given a DFA as a black-box D. You know the number of states D has, denoted q, and the alphabet of D, denoted S with s symbols, and you can “call D on any string x” and observe whether D accepts x or not (you cannot see its transition function. Assume that running D on any x takes O(n) time where n denotes |x|.

Write 2^poly(q,s)-time algorithms for performing the following tasks in the above black-box model. Analyse their complexity and justify why they are correct (it is not mandatory for complexity to depend on all of q, n, and s).
    (a) Determine whether a given DFA D accepts infinitely many strings.
    (b) Given two DFAs D1 and D2 (with q1 and q2 states), determine if there is some string that neither of them accepts. Hint: Product automaton.