Decide whether a context-free languages can be accepted by a deterministic pushdown automaton - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:12:37Z https://cs.stackexchange.com/feeds/question/1972 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/1972 21 Decide whether a context-free languages can be accepted by a deterministic pushdown automaton Andrew Tomazos https://cs.stackexchange.com/users/1577 2012-05-21T09:30:46Z 2012-05-23T13:37:24Z <p>Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)</p> <p>There <strong>may</strong> also exist a Deterministic Pushdown Automaton D that accepts exactly the language G accepts too. It depends on the grammar.</p> <p>By what algorithm on the productions of G can we determine if D exists?</p> https://cs.stackexchange.com/questions/1972/-/1973#1973 20 Answer by jmad for Decide whether a context-free languages can be accepted by a deterministic pushdown automaton jmad https://cs.stackexchange.com/users/82 2012-05-21T10:18:46Z 2012-05-23T13:37:24Z <p>There is no algorithm that given a context-free grammar, decide if a DPDA recognizes the same language and computes it if it exists.</p> <p>Because if such an algorithm existed, we would be able to decide the <a href="http://en.wikipedia.org/wiki/Context-free_grammar#Universality">undecidable problem of the universality of a context-free grammar</a> i.e. whether a given context-free grammar $G$ on $Σ$ recognizes the whole language $Σ^*$.</p> <p>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$.</p> <ul> <li><p>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 $Σ^*$.</p></li> <li><p>If a DPDA $A$ exists then we can decide if $L$ is equal to $Σ^*$ because universality is decidable for DPDAs. Why? Because:</p> <ul> <li>DPDA languages are closed under complementation (because DPDAs are deterministic)</li> <li>emptiness is decidable for DPDAs (because <a href="http://en.wikipedia.org/wiki/Context-free_grammar#Undecidable_problems">it is for PDAs</a>)</li> </ul></li> </ul> <p>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.</p>