Use the construction algorithm given in the proof of Kleene's theorem to construct an automaton (NFA) for the regular expression ((ab)*b + ab*)*. 4. Assume L = {a^ib^jc^k | k = i + j}. a. Show L is context-free by giving a context-free grammar that generates the language. b. Use the CFG from to give a pushdown automaton that recognizes L. 5. Let L be the set of strings over {a, b, c} where the number of as equals the number of as which equals the number of cs. Use a pumping lemma to show that L is not a regular language. (Of course, you can show that the language is not a CFL which implies that it is also not regular.) 6. Consider a Pushdown Automaton with 2 stacks (called a PDA2). It works similarly to a PDA, except at each move the automaton will check the state, input and the tops of both stacks. It then will move to a new state and perform stack operations (push-pop-null) on both stacks. Show that a PDA2 is more powerful than a PDA by giving a PDA2 in TABLE FORMAT to recognize L = {a^nb^nc^n | n > 0} which is not a CFL. Note your table must include listing both stacks twice: ( state - input - stack1 - stack2 - nextstate - stack1 op - stack2 op)