patternMajor
Decide whether a context-free languages can be accepted by a deterministic pushdown automaton
Viewed 0 times
canfreelanguagesacceptedpushdowndecidedeterministiccontextwhetherautomaton
Problem
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?
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?
Solution
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:
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.
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.
Context
StackExchange Computer Science Q#1972, answer score: 21
Revisions (0)
No revisions yet.