[Solved]: Push Down Automatons "guess" - what does that mean?

Problem Detail: 

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.

Asked By : cups

Answered By : jmite

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.

Best Answer from StackOverflow

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