Answer Happy

2. 65 points. Choose 2.a or 2.b, but not both. 2.a = {C,A,G,T}, L = { W: W = CAİG"IMC, m = j + n }. For example, CAGTTC E L; CTAGTC € L because the symbols are not in the order specified by the characteristic function; CAGTT & L because it does not end with c; and CAGGTTC E L because the number of T's do not equal the number of A's plus the number of G's. Prove that L & RLs using the RL pumping theorem. 2.b An instance of the problem AlmostSAT is a CNF Boolean formula containing at least 2 clauses, plus the index number of a clause in that formula. For example an instance of AlmostSAT could be represented as: '(X2 OR X3) AND (NOT X3) AND (NOT X2); 1' A positive instance is one in which there is a variable assignment that satisfies all the clauses, except possibly the one specified by the index number. The example above is a positive instance of AlmostSAT because '(X2 OR X3) AND (NOT X2)' can be satisfied by setting X2 to False and X3 to True. Like SAT, a positive instance of SAT-ɛ is a satisfiable CNF Boolean formula. The only difference is that an instance of SAT-E must contain at least one clause. Prove that AlmostSAT and SAT e are polyequivalent. That is, prove that AlmostSAT Sp SAT-a, and that SAT E S AlmostSAT. (Show that positive instances can be mapped to positive instances, negative to negative.)