3
$\begingroup$

Wikipedia Pushdown automaton (as of aug 16, 2013) states:

In general, pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations. If only one computation exists for all accepted strings, the result is a deterministic pushdown automaton (DPDA)

My professor gave this as an example that we shouldn't trust Wikipedia but rather consult a textbook. Is he right?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Just a remark (more for your professor): You don't have any guarantee that the textbook is always right either. Moreover, if you spot something wrong in wikipedia - fix it. $\endgroup$ – A.Schulz Aug 17 '13 at 6:59
  • 1
    $\begingroup$ @A.Schulz My professor said he rewrote part of Wikipedia, but some details were "improved" by others. He also agrees with you on textbooks. $\endgroup$ – Hendrik Jan Aug 17 '13 at 11:19
6
$\begingroup$

Yes, this is an example of an informal explanation that is not quite true.

A PDA is deterministic if (at any moment) it can make at most one legal computational step. This is a local property, a condition on a single step, and not on a computation.

The statement "If only one computation exists for all accepted strings" is a global property, a statement on all computations on a given string.

Let me give an example where the two concepts differ. The language of all (even length) palindromes over $\{a,b\}$ is context-free. It is accepted by a PDA in the obvious way. Start copying the input to the stack, guess the middle, then check whether the rest of the input matches the first part read (in reverse), finally accept on the empty stack. This automaton has only one accepting computation on each palindrome, but certainly is not deterministic.

But here I have argued that "only one accepting computation" is not the correct statement, where Wikipedia does only insist on a single computation (without the condition of acceptance). So is Wikipedia right after all? Unfortunately, no. The problem is in the $\varepsilon$-transitions. It is quite legal for a deterministic PDA to have the possibility of making several $\varepsilon$-moves before and after acceptance, it may even loop. That means many accepting computations on a fine deterministic PDA. It is also the reason that some proofs on PDA need just some extra care.

You may now edit Wikipedia to correct this mistake!

Improve this answer
$\endgroup$
1
  • $\begingroup$ To be fair, there are frequently several definitions for things around. They may be equivalent in terms of power, but not in technical terms. In order to show that the given sentence is wrong, we need the "definition" of computation, acceptance and deterministic PDA. (You assume the (one?) typical definition, which is fair.) $\endgroup$ – Raphael♦ Aug 17 '13 at 12:10

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.