CS 520 – Problem Set II Name ______________________1. Let = {a,b}. Define in set notation the following languagesa. * - i = i= 3 to b. * + = c. 2 - {aa,ab,ba} = __d. * = 2. a. Argue as to why it is possible to design an FA to accept thefollowing languageL = { w {a,b,c}*| (na(w) + nb(w)) mod 3 > nc(w) mod 4 }.b. How many states would this dfa have? Support your answer.3. For each of the following languages, prove that it is a regular language byconstruction or cogent argument or prove that it is not, by careful application ofthe pumping lemma. You may also use any results we obtained in class.a. L = { akblcm | k+l+m < n, n }b. L = { anbncndn | n 0 }CS 520 – Problem Set II Name ______________________4. For the following languages, prove whether they are context free. Assume ={ a,b }.a. L1 = { anbm | n 2m }b. L2 = { wwrwwr | w * }5. Consider the following CFG. Transform this grammar into Chomsky NormalForm. Be sure to remove lambda and unit productions before proceeding.S abABA bAB | B BAa | A | 6. Describe the strategy for building a Turing machine to accept the followinglanguageL = { w ai | i = 2 k, where k is a nonnegative integer