Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b [duplicate]

Question

How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$?

I'm sorry I can't give any approach of what I did, but it's because I don't even know where to start with this ex. in particular. I tried to search anything on my books, but couldn't find nothing at all. Any suggestion is welcome.

Answer 1

The idea behind the construction is very simple: when the number of $a$'s and $b$'s read so far is equal, the stack will contain $\bot$. When $k$ more $a$'s were read, the stack will contain $\bot A^k$. When $\ell$ more $b$'s were read, it will contain $\bot B^\ell$.

Our automaton will accept by clearing the stack. We assume that the stack is initialized with $\bot$. The automaton has a single state and the following transitions:

• When reading $a$ and the top of the stack is $\bot$, replace it with $\bot A$.
• When reading $a$ and the top of the stack is $A$, replace it with $AA$.
• When reading $a$ and the top of the stack is $B$, replace it with $\epsilon$.
• When reading $b$ and the top of the stack is $\bot$, replace it with $\bot B$.
• When reading $b$ and the top of the stack is $B$, replace it with $BB$.
• When reading $b$ and the top of the stack is $A$, replace it with $\epsilon$.
• There is an $\epsilon$ transition which, when the top of the stack is $\bot$, replaces it with $\epsilon$.

The final transition is used when the input is exhausted, to conform with the acceptance condition of emptying the stack. If we want to use acceptance by final state, we need to add a new state which will be the only final state, and modify the last transition by transitioning into this state.