Push Down Automatons "guess" - what does that mean?

Question

I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted by a deterministic pushdown.

Still, I do not understand how exactly they "choose". For palindormes for example every source I found just says the automaton "guesses" the middle of the word. What does that mean?

I can think of several possible meanings:

1. It goes into one state randomly and therefore might not accept a word, which actually is in the language

2. It somehow goes "every possible way", so if the first one is wrong it tests if any of the other might be right

3. There is some mechanism I am not aware of, that chooses the middle of the word and is therefore not random, but the automaton always finds the right middle.
   

This is just an example; what I want to know is how it works for any automaton that has several following states for one and the same state before it.

Answer 1

Quite simply, the mechanism is magic. The idea of non-determinism is that it simply knows which way it should take in order to accept the word, and it goes that way. If there are multiple ways, it goes one of them.

Non-determinism can't be implemented as such in real hardware. We simulate it using techniques such as backtracking. But it's primarily a theoretical device, which can be used to simplify the presentation of certain concepts.

For the palindrome, you can think about it in two ways. Either there's a magical power that lets your machine say "this is the middle of the word, time to switch from pushing to popping", or after reading each letter, it says "I'm going to fork a new process which that this letter is the middle of the word, and see if it finds it's a palindrome. Then in this other thread, I'll keep trying, assuming this isn't the middle of the word".

Another way to think of it is as infinite parallelism. So an equivalent model would be that, instead of choosing a new path, it simultaneously tries both paths, branching off new "processes," succeeding if any are in a final state after reading the whole word. Again, this can't be built using real hardware, but can be modelled with non-determinism.

The interesting thing about nondeterminism is that for finite-automata and Turing machines, it doesn't increase their computational power at all, just their efficiency.

Answer 2

The main difference (in my opinion) between a deterministic automaton and a non-deterministic automaton is that for a deterministic automaton a given input word has only one path through the machine. In a non-deterministic automaton a given input word may have multiple paths through the machine (because there may be choice at some points).

In light of this, the condition for acceptance of an input word also needs changing to accommodate the fact that a word may induce several paths through the machine. The usual definition of acceptance for a non-deterministic automaton is as follows: For a word to be accepted by the automaton there must be at least one accepting path induced by that word.

This then leads to the idea of an automaton "guessing," if a word is accepted by a non-deterministic automaton then we tend to think of the automaton as automatically making the right choices so that (one of) the accepting path(s) is followed when that word is presented as input.

What this means for palindromes is that the pda will essentially have two modes: a pushing mode where it pushes the current letters on the stack and a popping mode where it pops those letters off and matches them against the input. This machine will have an empty transition from the pushing state to the popping state which it will be able to follow at any point in the word. However the machine will only empty its stack and move to an accept state if it has read a palindrome and followed the empty transition at the middle of the palindrome. Since we only require the existence of an accepting path we can say that the automaton "guesses" where the middle of the word is.

Answer 3

The idea of nondeterminism is quite simple: the automaton might have several next steps in certain situations. The automaton accepts if there is some (there might be several!) sequence of steps leading from the initial configuration to an accepting one, it rejects only if there is no such sequence.

This means it "decides" which step to take next in those ambiguous situations. One way to talk about this is to say it magically selects the "right" next step always (or one, if there are several "right" steps). Another way to see it is that in such situations the automaton's computation splits into several copies, each one pursuing one path.

In practice, this can be implemented by backtracking, placing some form of tag on places where decision was taken, and go back and try the next alternative if the current path doesn't work out. This is usually handled by recursion. Or supplementing the information the automaton has "legally" with extra information (that is what you do when you show how a nondeterministic automaton works on the blackboard, looking ahead and figuring out which of the steps leads to success).

Answer 4

"Guessing" is directly related to our existential interpretation of non-determinism

In a nutshell: This idea that a non-deterministic automaton can guess (or be helped by an oracle) is directly related to our existential interpretation of non-determinism. Another interpretation is possible (maybe others) where "guessing" would not make sense.

Non determinism is strange. We do have one way of interpreting it in automata theory, but it is not a priori obvious how we should do that.

It may seem surprising, but non-determinism is a very common situation. When one has to prove a theorem, given the axioms of some mathematical theory, the process is naturally a non deterministic one. That is why we often do not know what to do to solve a problem, for example to find the solutions of a third degree equation, or prove some theorem.

There are many ways to combine what is already known with inference rules to get new results. And the situation is usually the same if we try to reconstruct a proof backward from the result.

When attempting to solve such a problem, we try to "guess" a path in some transition system.

Actually, we do not guess, but build in our mind some structure that organizes and/or simplifies the maze of possibility so that we can see our path through it. In some cases, the question follows an identified pattern for which we have a standard way to (sometimes? usually? always?) find a solution, and we call that an algorithm.

One (usually expensive) technique we can use is simply to fully explore the maze: to follow all paths, doing it breadth first to avoid being caught in an infinite subgraph. This is pretty much what is being done by dovetailing all possible computations of a non-deterministic automaton. This derived dovetailed computation is itself a deterministic one.

This dovetailed computation $DC$ mimics all possible computations of the original automaton $A$, but does not tell us how it should be interpreted. It can just tell us whether A might sometime halt, with acceptance or rejection, and possibly that it will always halt. But it cannot, any more than $A$ itself, tell us that $A$ never halts, or never halt with acceptance.

Actually, there could be different ways of interpreting a non-deterministic computation. Afaik they are all consistent, but not with each other.

In the case of a language recognizer $R$, such as a NPDA, that can either not halt, or halt with acceptance or rejection, the recognizer is said to accept an input $w$ iff there is one computation that halts and accept. This is consistent with our own view of the non-deterministic proof process that is considered successful iff it can identify one proof tree for the theorem to be proved.

The idea of guessing for the recognizer is just an image taken from our own way of "guessing" how to find that proof tree. But the big difference is that our brains are not PDAs. They are much more complex devices with the ability to explore and map approximately transition structures so that we can find our way through them, which we sometimes perceive as guessing.

This interpretation of non-deterministic computation is what I would call existential acceptance, in reference to the fact that it requires only the existence of a single accepting computation. It corresponds to existential halting that I introduced in another answer.

However, one could also interpret non-determinism in a universal way as: a recognizer is said to (universally) accept an input "w" iff all possible computations halt and accept the input. This universal acceptance corresponds to the concept of universal halting introduced in the same answer.

Universal acceptance, and universal halting seem to lead to a self-consistent understanding of non-determinism. Hence one could do theoretical work with that definition. But it is not consistent with our usual practice in many non-deterministic situations such a theorem proving, or in everyday life situation. When confronted with a problem, we only want one way of solving it, and then do not care whether other ways are successful or not (well this is a bit over simplified).

If we have to recognize a palindrome, we can guess by measuring the length and looking for the middle. The PDA cannot. But, as we are only interested in existence of one solution, we can always pretend that it can ... if that will help it. Or we can consider that it has oracles provided by more intelligent machines (us?) to help it. Or you may even call it magic, and think it is (after all, the existential quantifier is a kind of magic wand). If it can help, it will. If there is no accepting computation, no help whatsoever will be any use.

Note that this idea of guessing would be meaningless in the universal acceptance interpretation.