1. Give a pushdown automaton that that accepts exactly the strings with correctly matched parentheses in the alphabet containing just two symbols, left and right parentheses ? = {(,)}. Explain your construction.

2. Give a pushdown automaton that accepts exactly the strings over ? = {a, b} that contain the same number of a's and b's. For example, aabbaabbab is accepted but aba is not. Also bbbbaaaa and aaaabbbb are both accepted. Explain your construction.

3. Give a pushdown automaton that accepts strings in the alphabet ? = {a, b,),(} such that the parentheses are correctly matched, and between each left parenthesis and the next right parenthesis, and in the whole string, there are equal numbers of as and b's.

For example, ((abab)(ab)) is accepted but ((aab(ab)) is not accepted. Also ((abab)ab(ab)) is accepted, but not ((abab)aba(ab)). The stated conditions guarantee that, as you proceed from left to right, each time you encounter either kind of parenthesis, the numbers of a's and b's already processed are equal. Explain how ((abab)ab(ab)) is accepted by your PDA, and ((abab)aba(ab)) is not.