Or in other words that $\forall L: L \in DCFL => L \in CFL$. First of all, does this statement even require a proof?
My idea was to let L be an arbitrary language, such that $L \in DCFL$, this implies that there is a DPDA that accepts L. If I can transform a PDA, which accepts input when that input empties its stack, into a PDA that accepts by accept states, then I would have shown that L will also be accepted by that new PDA, right?
Now the question is, how can I transform a PDA that accepts by empty stack into one that accepts by accept states?
The reason why we needed to introduce accept states for DPDAs in the first place, was that if a DPDA could only accept input that leads to an empty stack, then only prefix-free languages could be accepted by a DPDA. My question now is whether the fact that a PDA by nature is non-deterministic actually solves this problem, meaning that since it can have multiple transitions for a given configuration, I could create paths that accept strings that do contain prefixes. If that would be the case, there really wouldn't be any reason to transform a PDA into one with accept states, since a PDA in its normal form should be able to recognise all languages that are in DCFL.
Therefore my question, do I necessarily have to introduce accept states into a DFA to make sure that it recognises all deterministic context free languages or can it accept all of those languages anyway, i.e. when it accepts by an empty stack?
If I don't necessarily need accept states in a PDA to accept all $L \in DCFL$, could I simply enter another $\epsilon$ transition of this form: $\delta(q,\epsilon,\epsilon)$->$(p,\epsilon)$, meaning that if a PDA is in state q, a non-accept state, and it's stack is empty, then I could send it into accept state p, also with an empty stack?
Would that create a PDA that accepts by accept state and would that prove that a PDA with accept states accepts all context free languages?
Best Answer
If you have a PDA $A$ that accepts by empty stack you can turn it into an equivalent automaton $B$ using accept/final states. (Some texts explain that both types of PDA are equivalent. Not as you note for DPDA because of the prefix property.)
The new machine $B$ starts from a new initial state and as a first step pushes a new special bottom-of-stack marker $\Box$ under its initial stack symbol $Z$ (by popping $Z$ and pushing $\Box$ and $Z$ back). Now $B$ simulates $A$ using the same instructions and states. Whenever $A$ has empty stack (and is ready to accept, when its input has been read) then $B$ recognizes this because it "sees" the $\Box$ as topmost stack symbol. Then it moves to the newly introduced accept state.
I hope this answers your questions?