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 aword, which actually is in the languageIt somehow goesevery possible way, so if the first one is wrong it tests if anyof the other might be rightThere is some mechanism I am notaware of, that chooses the middle of the word and is therefore notrandom, 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.
Push Down Automatons guess - what does that mean?
automata;pushdown automata;nondeterminism
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.