Please solve complete

3. (a) Let n > 0 be an integer and Ln be the language of all linear equations Q1X1 + a2X2 + ... + arXn + an+1 = 0 in n unknowns X1, X2,..., Xn and over integer coefficients (1,22,..., 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 az X1 + a2X2 + ... + arX, +an+1 = 0 with 21, 22, ..., On, Qn+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 linear equation 01X1 +42X2 + ... + anX + an+1 = -0, (b) with aj, a2,..., An, An +1 in the integers, decides whether or not it has an integer solution, and if it does, finds at least one such solution. [5] 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 = \ulo = 1Wc} (7) (ii) {w e {a,b,c}* | it is not the case that wla = |wli = wc} [3] Note that we use the notation Wla to denote the number of occurrences of the letter a in w, and similarly for wo and We. = = =