Consider the NTM defined by = { 0 }, = { 0, a1, a2, _ } ("_" denotes the blank symbol), Q = { q0, qaccept }, and

(q0, 0) = { (q0, a1, R), (q0, a2, R), (qaccept, 0, R) } (q0, _) = { (qaccept, _, R) }

Given an input string 0n, n 0, this NTM nondeterministically writes a string x {a1, a2}* such that 0 |x| n. Give the computation tree of configurations starting with q000 at the root.

"_" denotes the blank symbol.

Give the exact number of branches of the computation tree on input string 0n, n 0. Justify your answer. Give the exact worst-case time complexity function, WM(n), of this NTM. Justify your answer. Modify this NTM to one which, given an input 0n (n 0), nondeterministically writes a string x {a1, , ak}* such that 0 |x| n.