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:
It goes into one state randomly and therefore might not accept a word, which actually is in the language
It somehow goes "every possible way", so if the first one is wrong it tests if any of the other might be right
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.
