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?
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?
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$.
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.