Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)There may also exist a Deterministic Pushdown Automaton D that accepts exactly the language G accepts too.  It depends on the grammar.By what algorithm on the productions of G can we determine if D exists?
Decide whether a context-free languages can be accepted by a deterministic pushdown automaton
automata;context free;pushdown automata
There is no algorithm that given a context-free grammar, decide if a DPDA recognizes the same language and computes it if it exists.Because if such an algorithm existed, we would be able to decide the undecidable problem of the universality of a context-free grammar i.e. whether a given context-free grammar $G$ on $$ recognizes the whole language $^*$.Suppose there is such an algorithm $A_{DPDA}$. Let $G$ be some context-free grammar. Let $L$ be $\mathcal L(G)$. Then the algorithm $A_{DPDA}$ will decide if there is a DPDA $A$ recognizing $L$.If there is no such DPDA, then $L$ is not recognizable by a DPDA, in particular it is not regular, so it can't be $^*$.If a DPDA $A$ exists then we can decide if $L$ is equal to $^*$ because universality is decidable for DPDAs.Why? Because:DPDA languages are closed under complementation (because DPDAs are deterministic)emptiness is decidable for DPDAs (because it is for PDAs)Using $A_{DPDA}$ we have built an algorithm deciding whether $L(G)=^*$ for any context-free grammar $G$, which has been proven impossible. Therefore $A_{DPDA}$ does not exist.