0
$\begingroup$

[1] gives an example for PDA which contains rules of:

(p,e,Z,q,Z)
(p,e,A,q,A)

and says,

The third and fourth instructions say that, at any moment the automaton may move from state p to state q.

So, how does PDA know when it needs to move from a state to another?

[1] https://en.m.wikipedia.org/wiki/Pushdown_automaton

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't think the phrase "at any moment" signifies any ambient time ticks. It is supposed to be read as "if the automaton is in state p then it can transition to state q under no additional constraints" $\endgroup$
    – Apoorv
    Apr 20 at 20:01
  • $\begingroup$ So, if I have a PDA and an input string which the PDA accept, a single run of the PDA, e.g: answer=PDA(input), may give me a wrong answer? $\endgroup$
    – Doerthous
    Apr 20 at 21:01

1 Answer 1

Reset to default
2
$\begingroup$

Quoting the same Wikipedia page (emphasis mine):

If, in every situation, at most one such transition action is possible, then the automaton is called a deterministic pushdown automaton (DPDA). In general, if several actions are possible, then the automaton is called a general, or nondeterministic, PDA. A given input string may drive a nondeterministic pushdown automaton to one of several configuration sequences; if one of them leads to an accepting configuration after reading the complete input string, the latter is said to belong to the language accepted by the automaton.

A concept of determinism is applied to multiple structures in Computer Science, e.g. automata and Turing machines. In general, an automaton is called deterministic when there is exactly one transition from every state. All actions are determined, there is a single computation path, and the automaton either accepts the string or does not.

In contrary, nondeterministic automata may have several distinct transitions from some states. Each transition gives a different computation path, so the path is not determined by the input anymore but there may be multiple paths corresponding to a certain input. There are several ways to define the language with regard to nondeterministic automata, but the most common one is to require having at least one accepting path. (The other way may be to require all paths to lead to accepting state, not a single one, thus replacing $\exists$ with $\forall$; it may be convenient in defining complexity classes like co-NP.)

You may interpret it as guessing: whenever you meet a state with multiple transitions, you make a guess and pick an arbitrary one. The word is accepted if it is possible to make correct guesses and arrive to the accepting state.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I can image the random pick, but I can't figure out how this random pick implementation work (how this should be done in code?). If a random pick failed, then the PDA retry until it try all path, and finally yield an accepted or non-accepted answer? $\endgroup$
    – Doerthous
    Apr 20 at 20:53
  • $\begingroup$ @Doerthous Nondeterministic automata do not provide explicit accepting paths. They only define a language as the set of words for which an accepting path exists. There is no direct implementation implied. Of course, you can backtrack all paths until you find an accepting one (or prove its nonexistence). Whether it can be done efficiently is a complicated problem. I can't tell about PDAs, but the equivalent problem for Turing machines - given a (polynomial time) nondeterministic machine that accepts the given input, find the accepting path - is a famous P vs NP problem. $\endgroup$
    – Ivan Smirnov
    Apr 20 at 22:42
  • $\begingroup$ Consider an example from first-order arithmetics: we can define the predicate "number $x$ is composite" as $\exists y: 1 < y < x \vee x \mod y = 0$. However, this definition does not provide us with efficient ways of computing $y$ given $x$. $\endgroup$
    – Ivan Smirnov
    Apr 20 at 22:46
  • $\begingroup$ Replace $\vee$ with $\wedge$, that's a typo. $\endgroup$
    – Ivan Smirnov
    Apr 20 at 23:02

Your Answer

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

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