Construct a Deterministic Pushdown Automaton for unequal number of elements

Question

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?

Answer 1

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.

Answer 2

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.