# Deterministic Pushdown Automata that accepts #a = #b

I am trying to create a DPDA that accepts words from the following Language:

$$L = \{wx \; | \;w \in \{a,b\}^*, \#a = \#b \}$$

My intuition was to initially put an $$x$$ on the stack and then write an unlimited amount of $$a$$ or $$b$$, while both operations put an $$B$$ or $$A$$ on the stack. Then, in the second last state we can write an limited amount of $$a$$ and $$b$$ for popping an $$A$$ or $$B$$ from the stack.This ensures that the amount of $$a$$ and $$b$$ are equal before we can read the initial $$x$$ from the stack. As a last step, we read $$x$$ as the last element of the stack. However, building this determinstic seems too complex. Any hints?

• Is $x$ a string in $\{a, b\}^*$ or a single letter? If the latter, the PDA is really simple. Jun 11 at 14:49
• a single letter.
– dnr
Jun 11 at 15:57

You have to keep track of $$\#a - \#b$$ at each point of the input. This number can become negative, so say the number of excess $$a$$ is represented by that many $$A$$ on the stack, and the number of excess $$b$$ by $$B$$s. If at the end of the string there is no excess (empty stack), accept.
Reading a $$a$$ and a $$b$$ should "compensate" each other. For example, reading a $$a$$ could push a $$A$$ or remove a $$B$$ depending on the stack, and conversely when reading a $$b$$.
• but if they only compensate each other, and let's say $b$ pushes $A$ on the stack and $a$ pops that $A$, I would not be able to read $baaaaabbbb$. If that is was your suggestion.
• Your proposition is not very logical and is not what I proposed. When reading $baaaaabbbb$, what I propose is push a $B$, then remove a $B$, then push a $A$ four times, then remove a $A$ four times. That's why I added "depending on the stack". Jun 11 at 13:58