For each language given, write "REG" if the language is regular, write "CF not REG" if the language is context-free but not regular, write "R not CF" if the language is recursive but not context free, write "RE R" if the language is recursively enumerable but not recursive, and write "not RE" if the language is not recursively enumerable. (a) The set of all strings over the alphabet (a, b, c) where are not of the form a "b"c" (b) The 0-1 Traveling Sales man Problem (c) The diagonal language 2 Recursively enumerable sets 123 2. (a) Let BCN and let n > 1; prove that if B is recursive then the predicate M(x,...,xn) given by M(x,...,xn) = 2*3*2...pe B is decidable. (b) Let AN"; define A to be recursive if the predicate 'xe A' is decidable. Prove that A is recursive iff (2*13*2...p: (x,...,xn) E A} is recursive.