Creating a Deterministic Push Down Automata

Problem Detail: 

I saw this old post on stack overflow of a PDA that accepts a language where there are exactly twice as many a's as there are b's. The image they used is below and so is the link to the post itself.

PDA for language that accepts twice as many a's as b's.

It was commented that the PDA was not deterministic. So I'm wondering what exactly makes a PDA deterministic, for example, would you remove the epsilon transitions here to make it deterministic or what?

If somebody could convert this into a deterministic PDA and explain the steps to do so, I would appreciate it, I'm pretty lost when it comes to push down automata.

Asked By : navlag

Answered By : Raphael

Just like any automaton, a PDA is nondeterministic if (and only if) the transition relation is not a function, that is there are configurations that have multiple possible succeeding configurations. If this is the case for reachable configurations, this means that a non-deterministic automaton has inputs for which there are multiple computations.

Here, the transition $(\varepsilon, Z0/Z0)$ to state three may be taken even though the word has not been completely read, that is in configurations of the form

$\qquad (\alpha 1 \beta, Z0)$

you can either take transition $(\beta_1, Z0/\beta_1Z0)$ or $(\varepsilon, Z0/Z0)$ -- the automaton is non-deterministic. Of course, taking the latter always leads to rejecting the input unless $\beta = \varepsilon$, Since there is no other nondeterminism, this implies that the automaton is unambiguous.

Converting an NPDA to a DPDA is not always possible; NPDA define a properly larger language class than DPDA. Given an NPDA, checking if an equivalent DPDA exists is undecidable. And even if there is one (and you know that) there is no algorithm to find it. That is to say, there is no general, algorithmic technique for that part of your question.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21518