0
$\begingroup$

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

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

enter image description here

Or can anyone check if the following solution is correct?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – John L. Oct 23 '18 at 22:46
  • $\begingroup$ 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. $\endgroup$ – D.W. Oct 24 '18 at 19:04
0
$\begingroup$

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.
$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 :) $\endgroup$ – BrandNewStory Apr 1 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.