2. Let = {a, b,c}. We know that {w | w {a,b}*} is regular as it can be recognized by a FA {wwR | w {a,b}*} is context free as it can be recognized by a PDA {ww | w {a,b}*} is not context free as it cannot be recognized by a PDA At the same time, we recall that NFAs were generalized to PDAs by adding one stack. Idea: Can PDAs in turn be generalized by adding even more stacks? Suppose we have two stacks, so that the transitions in the state diagram are indicated with b, (c, C) (e, 2), where b is the input symbol read, (c, c) denote the symbols at the top of the stack 1 and 2, respectively, and (e,e2) are symbols pushed back to the corresponding stacks. As before, any of the (b, c1, C2, e1, e2) can be e indicating that the corresponding parameter/operation is omitted. Draw a state diagram for two-stack PDA that recognizes {ww | w {a,b}*}. Note: consequently, you show that the second stack improves the computational capacity!