2. (40 pt., 10 pt. each) Give an implementation-level description of a Turing machine that

decides each of the languages in Problem 1.

a. A = {w = {a,b}* | w contains at least one a and at most one b}

b. B = {w = {a,b}" | w contains more a's than b's}

c. C = {a¹b/citii,j ≥ 0}

d. D= {01m|n, m≥ 0 and n is divisible by m}

For example, 000011 € D (because 4 is divisible by 2) and 00011 # D (because 3 is not

divisible by 2).