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$
  • 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.
| cite | improve this answer | |
$\endgroup$

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.