Problem Detail: 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?
Asked By : Andrew Tomazos
Answered By : jmad
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1972
