# 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.

The answer in that image is actually not a deterministic PDA, because in the definition of DPDA, the transition functions need to satisfy the following rules: 1. $$\delta(q, a, b)$$ contains at most one element; 2. if $$\delta(q,\lambda,b)$$ is not empty, then $$\delta(q,c,b)$$ must be empty for every $$c\in\Sigma$$. These two rules prevent multiple paths for same input symbol and stack symbol (to make it deterministic). From the PDA in the question, there are some transitions like $$\delta(q_0,a,b)$$ and $$\delta(q_0,\lambda,b)$$, which does not satisfy the second rule.

There is one way to get the DPDA for this language $$L=\{w: n_a(w)\neq n_b(w)\}$$, which is to get the DPDA of the complement of $$L$$ first, and that is $$\bar{L}=\{w: n_a(w)=n_b(w)\}$$. Then you can simply convert the final states to non-final states and vice versa. The DPDA for $$\bar{L}$$ is very similar to the one in the question, except that the transitions from $$q_0$$ to $$q_1$$ should be changed to $$\delta(q_0,\lambda,＄)=(q_1,＄).$$ After that, changing $$q_0$$ to a final state and $$q_1$$ to a non-final state and you will get the correct answer. This method is based on the closure property for DCFL that DCFL is closed under complementation.

• I don't know why the last transition function is in a bad format, it should be $\delta(q_0,\lambda,\$)=(q_1,\$)$. I'd appreciate it if someone can help me fix that display issue :) – BrandNewStory Apr 1 at 18:41