Build a multi-stack Push Down Automata (PDA) (it means you can use more than one stack, for example 3 stacks) to accept the language {a"b"a"b" | n21} over the alphabet E={a,b}. Please explain your design shortly and draw the PDA.

We can clearly see that the language is not possible to be constructed by a Single stack but it can be constructed by using the two stacks.

In the above PDA, the first n a's are being accepted in the first state i.e q0. And while accepting the a's we didn't push anything in Stack 2. The no. of a's read pushed to the Stack 1.

Now, in the state q1, we will read all the b's. For that reading each b, we will pop one a from Stack 1 and for that, we will push b in the Stack 2. So, after reading all b's Stack 1 will empty and Stack 2 will contain n b's.

In the state q2, we will read all the a's. For that reading each a, we will pop one b from Stack 2 and for that, we will push a in the Stack 1. So, after all a's Stack 2 will empty and Stack 1 will contains n a's.

In the state q3, we will read all the b's. For that reading each b, we will pop one a from Stack 1 and will not change Stack 2.

At last, when both Stack 1 and Stack 2 will be empty the string will reach into the accepting state.