I realize non-deterministic automatons can be an improvement over deterministic ones as they can "choose" among several states and there are some languages which cannot be accepted by a deterministic one. 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. Can maybe someone help out?

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.