Are Acceptance by Final State and Acceptance by Empty Stack equivalent in language recognition power for Nondeterministic PDAs?
Any NPDA accepting by final state can be converted into an equivalent NPDA accepting by empty stack, and vice versa.
In a Pushdown Automaton, how does a move depend on the current configuration?
PDA transition function $\delta (q, a, X) looks$ at control state q, input symbol 'a' (or $\epsilon$), and top stack symbol X.
Are Deterministic Pushdown Automata (DPDA) and Nondeterministic Pushdown Automata (NPDA) equal in language recognition power?
$NPDAs accept all Context-Free Languages (e.g. even palindromes {w w^R}), whereas DPDAs accept only Deterministic CFLs.$
Which conversion between automata classes is NOT algorithmically possible?
Not all CFLs are Deterministic CFLs (e.g. $L = {w w^R}$); hence NPDA cannot be algorithmically converted to DPDA in general.
What computational model is formed by equipping a Pushdown Automaton with TWO STACKS (Two-Stack PDA)?
A two-stack PDA can simulate an infinite Turing Machine tape by using one stack for the tape left of head and the second stack for the right.