# Construct a Deterministic Pushdown Automaton for unequal number of elements

Can anyone help me construct a deterministic PDA for the following language:

$$L=\{w\in(a,b)^* \mid \#_a(w)\neq \#_b(w)\}$$

Or can anyone check if the following solution is correct?

• Here is an answer at stackoverflow to a question on pushdown automation with unequal elements by @Patrick87. The PDA constructed in that answer is in fact a DPDA. – John L. Oct 23 '18 at 22:46
• Comments are not for extended discussion; this conversation has been moved to chat. If you want to clarify your question, please do that by editing the question, not by leaving a long comment thread with your train of thought. – D.W. Oct 24 '18 at 19:04

The image in the question shows a correct construction of a deterministic pushdown automaton (DPDA) for the language of unequal number of $$a$$'s and $$b$$'s, as the OP and I have come to an agreement in a long discussion.
Please note that in OP's notation for DPDA, a fixed symbol $$Z$$ is at the bottom of the stack. The only case of an $$\epsilon$$-transition being used is when the stack top is $$Z$$.
The basic idea is to use the stack to record the difference of the number of $$a's$$ and the number of $$b's$$.
• If the symbol above $$Z$$ is $$a$$, then the stack does not contain $$b$$ and the number of $$a$$'s in the stack is how many more $$a$$'s have been fed to the DPDA than $$b$$'s.
• If the symbol above $$Z$$ is $$b$$, then the stack does not contain $$a$$ and the number of $$b$$'s in the stack is how many more $$b$$'s have been fed to the DPDA than $$a$$'s.