2. (20 points) The Pumping Lemma for Regular Languages can be used to prove that a language is not regular, by using it in a proof by contradiction. Prove that the language A = {02(io)" In >0} is not regular. The first step is done for you. a. Assumption: The language A is regular. (Therefore, it obeys the PL for RL, which is true for all Regular Languages.) b. By the PL, there must exist some length p such that for all strings s E A, if Isl p then the three conditions of the lemma are true. Choose a string s E A whose length is longer than p. S = C. The length of s must be 2 p. What is Is for the string you chose? Isi = d. Now show that any way of dividing s into xyz is doomed to violate at least one of the PL conditions. Consider the third PL condition: \xy Sp, which says that x and y must be chosen from the first p symbols in the string s. Construct a set of cases for how y can be chosen, given that x could be empty but y cannot be. Show for each case that if the string y is pumped, the resulting string is not in the language A. (Because the PL says it must be in A, this gives our contradiction.)