nondeterminism of a PDA
Like an NFA, a general pushdown automaton is nondeterministic: at a given moment it may have SEVERAL legal moves to choose from, and it accepts if SOME sequence of choices leads to acceptance. Picture it cloning itself to try every option in parallel, or imagine a lucky guesser who always picks the right branch when one exists. This guessing power, combined with the stack, is exactly what a PDA needs to handle some context-free languages.
Why is the guess essential here? Consider the language of even-length palindromes over {a, b} — strings like abba or baab that read the same forwards and backwards. To check one, a PDA pushes the first half onto the stack, then pops it while matching the second half against it; because the stack reverses order, this works perfectly. But the machine has no marker telling it where the middle is. It must GUESS, at some point, 'the first half is over, now start matching'. A nondeterministic PDA simply tries every possible midpoint at once and accepts if any guess pans out. There is no way to compute the midpoint in advance, so the guess is genuinely needed.
This is the moment where pushdown automata break from finite automata in a deep way. For finite automata, nondeterminism is only a convenience — every NFA can be converted to an equivalent DFA. For pushdown automata that is FALSE: the nondeterministic PDA is strictly more powerful than the deterministic one. Even-length palindromes are context-free and recognised by a nondeterministic PDA, yet no deterministic PDA recognises them. So here nondeterminism is not mere convenience; it adds real expressive power, and that asymmetry is one of the most surprising facts in the whole theory.
For even-length palindromes, at each position the PDA both continues pushing AND tries an ε-move to 'switch to matching mode'. One of those guesses corresponds to the true midpoint; if the string is a palindrome, that branch accepts.
Accept if SOME branch accepts. Guessing the midpoint is impossible to avoid — hence nondeterminism is essential here.
Unlike the NFA-to-DFA story, you CANNOT always determinise a PDA. Nondeterministic PDAs are strictly more powerful than deterministic ones — this is the key difference between finite and pushdown automata.