Describe a PDA that accepts all strings over $\{a, b\}$ that have as many $a$’s as $b$’s.

Question

I'm having my exam in few days and I would like help with this

Describe a PDA that accepts all strings over $\{ a, b \}$ that have as many $a$’s as $b$’s.

Answer 1

Hint: Use the stack as an indication of how many more of one symbol have been so far read from the string than the other. (Also ensure that the stack never contains both $\mathtt{a}$s and $\mathtt{b}$s at the same time.)

Answer 2

Hint:

Any word $w$ with same number of $\mathtt{a}$s and $\mathtt{b}$s can be split into words $w = w_1w_2w_3\ldots w_n$ such that no proper subword of $w_i$ has same number of $\mathtt{a}$s and $\mathtt{b}$s (if you were to graph the word, where $\mathtt{a}$ is $+1$ and $\mathtt{b}$ is $-1$, then the splitting points are exactly those where your graph hits zero). For any such a subword $w_i$ the letters $\mathtt{a}$ and $\mathtt{b}$ behave exactly like parentheses:

• $\mathtt{a}=\mathtt{(}$ and $\mathtt{b}=\mathtt{)}$ when there is always more $\mathtt{a}$ than $\mathtt{b}$,
• $\mathtt{a}=\mathtt{)}$ and $\mathtt{b}=\mathtt{(}$ when there is always more $\mathtt{b}$ than $\mathtt{a}$.

Good luck!