4
$\begingroup$

enter image description here

This is the PDA to accept strings with equal number of $a$'s and $b$'s. The $\epsilon$ transition in the first state is causing nondeterminism. When we have input a with Z at the bottom of the stack, then at the beginning it can do $(a,Z/aZ)$ or $(\epsilon,Z/Z)$ and go to final state, so automaton has 2 choices which can lead to 2 different states.

How do I convert it to DPDA ? How do I remove that $\epsilon$ transition from first state to make the PDA deterministic?

Here, the stack symbol is $Z$ and the transition $(a,Z/aZ)$ means on seeing input $a$ with $Z$ at the top of the stack, push $aZ$.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

The DPDA could be constructed by adding explicit states and dropping too permisive epsilon transition.

I will denote accepting state by paranthesis around the name.

$(q_0, \epsilon, Z, (q_f), Z) \text{ accept empty string}$
$((q_f), a, Z, q_a, a)\text{ add initial a (or after cancellation occurs)}\\ ((q_f), b, Z, q_b, b)\text{ add initial b (or after cancellation occurs)}\\ (q_a, b, a, q_a, \epsilon) \text{ even out two symbols}\\ (q_b, a, b, q_b, \epsilon) \text{ even out two symbols}\\ (q_a, \epsilon, Z, (q_f), Z) \text{ accept, it happens only with empty stack}\\ (q_b, \epsilon, Z, (q_f), Z) \text{ accept, it happens only with empty stack}\\ (q_a, a, a, q_a, aa)\text{ add another a to stack}\\ (q_b, b, b, q_b, bb)\text{ add another b to stack}$

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ If acceptance is possible with empty stack, then it should also be possible with final state. How can we draw a DPDA with final state acceptance for this language ? The only way I could think of is adding a delimiter at the end of the input (like a special character) to make it deterministic. But that would change the language. $\endgroup$
    – Sagar P
    Commented Jan 30, 2018 at 7:53
  • $\begingroup$ @SagarP While this equivalence holds true for NPDA, I'm not sure it holds for DPDA as well. The usual constructions introduce non-determinism, iir. $\endgroup$
    – Raphael
    Commented Jan 30, 2018 at 9:23
  • $\begingroup$ @Raphael, Yes the equivalence doesn't hold true. But I think if a language can be accepted by empty stack then it can be accepted by final state for DPDA but vice versa is not true because of prefix property. $\endgroup$
    – Sagar P
    Commented Jan 30, 2018 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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