21
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Even if you know beforehand that there is a DPDA for G, there is no algorithm to find it. See here. $\endgroup$ – sdcvvc May 21 '12 at 23:55
20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand this sorry. Are you using Σ to refer to the alphabet used by G? And what do you mean "is L the full language $Σ^∗$" ? Are you saying that we will execute the algorithm on a grammar G that generates $Σ^∗$, the language of any string over Σ? We would clearly find not only a DPDA, but a simple DFA for this language. The complement of $Σ^∗$ is the empty language, this is also easily recognized by both a DPDA and a DFA - so I am clearly missing something in your explanation. $\endgroup$ – Andrew Tomazos May 21 '12 at 16:34
  • $\begingroup$ I hope this is clearer now. Note that I answer a slightly different question: I would have sworn you asked if we could compute $D$, not just decide whether or not it exists. $\endgroup$ – jmad May 21 '12 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.