(a) Let n > O be an integer and Ln be the language of all linear equations ajX1 + a2X2 + ... + anXn+an+1 = 0 in n unknowns X1, X2,..., Xn and over integer coefficients a1, a2, ..., An, An+1, which have a solution in the integers. (i) Show that Ln is semi-decidable by describing, in general mathematical terms, an algorithm that takes as input a linear equation a X1 + a2X2+...+ anXn + an+1 = 0 with a1, 22, ..., an, an+1 in the integers, and halts exactly when this equation has a solution in the integers. [5] (ii) We now use the fact (stated in the lectures) that Ln is actually decidable. Describe an algorithm, using a decider for Ln as a subroutine, which for any a linear equation a X1 + a2X2 + ... + an Xn + an+1 = 0, with a1, a2, ..., An, Ant1 in the integers, decides whether or not it has an integer solution, and if it does, finds at least one such solution. [5] (b) Argue that the following languages over the alphabet {a,b,c} belong to the complexity class P. It is enough to give an implementation level description of the relevant Turing machines, and explain why their complexity is polynomial. (i) {w {a,b,c}* ||Wla = \Wl6 = [w]c} w | = [7] (ii) {w {a,b,c}* | it is not the case that |wla = |wl6 = \wc} [3] 3 Note that we use the notation wla to denote the number of occurrences of the letter a in w, and similarly for (w/o and Wlc. = = =