4
$\begingroup$

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.

enter image description here

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.

Improve this question
$\endgroup$
  • $\begingroup$ My cursory glance indicates that this is in fact deterministic. Unless, does $L$ denote the empty string? In that case, removing the empty transition would make it deterministic, if it can be removed without changing the language. Not all PDAs can be made deterministic (unlike finite automata) $\endgroup$ – jmite Feb 11 '14 at 4:52
  • $\begingroup$ yes, L is the empty string. $\endgroup$ – UndefinedReference Feb 11 '14 at 4:53
  • $\begingroup$ I think this language has been dealt with multiple times; check context-free. $\endgroup$ – Raphael♦ Feb 11 '14 at 7:09
  • $\begingroup$ @Raphael I think the real question here is, "What is the definition of a deterministic PDA and how can one convert a nondeterministic PDA to a deterministic one?" $\endgroup$ – David Richerby Feb 11 '14 at 8:34
7
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ "nondeterministic if (and only if) there are inputs for which there are multiple computations". Be careful! This might be read as "multiple successful computations" which is a mistake: a nondeterministic machine might have only a single successful computation (e.g., when guessing the middle). Also there might be two conflicting instructions in a state that is never reached. Technically that is nondeterminism but will not lead to multiple computations. $\endgroup$ – Hendrik Jan Feb 11 '14 at 12:03
  • $\begingroup$ @HendrikJan Quite true; I adapted my answer thus. Thanks! $\endgroup$ – Raphael♦ Feb 11 '14 at 16:09
  • $\begingroup$ I rolled back an edit because it did not address an inherent property of nondeterminism, but a feature of a particular definition. (Sometimes, deterministic automata are required to always have exactly one "live" transition until the word is empty, that is for the transition function to be total. That is not necessary, though; we can implicitly reject if there is no next configuration, even for DPDA.) $\endgroup$ – Raphael♦ Feb 11 '14 at 17:46

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.