Decide whether a context-free languages can be accepted by a deterministic pushdown automaton

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