Understanding DPA

Question

DPA denotes “Deterministic Pushdown Automata”.

Is the following (*) true regarding DPA:

After all symbols of the input sequence are consumed, the input sequence is accepted either (1) if the stack is empty or (2) if the current state of the DPA is an accepting one, or both.

My book is fairly vague on the subject (it doesn't mention it) and Wikipedia, in my opinion, doesn't offer a better explanation either:

There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by empty stack are the languages that are accepted by final state, as well as have no word in the language that is the prefix of another word in the language.

(What I don't understand is the equivalence they mention, and how does that influence the acceptance of a word.)

If my statement (*) doesn't hold, how would I determine, given the definition of a DPA, which condition are input sequences supposed to fulfill? Would I assume one or the other as the preferred one?

Answer 1

You can define the language of a PDA in two different ways:

1. For a PDA $M$, $L_1(M)$ is the set of all words which can be processed by $M$ in such a way that at the end, the stack is empty.

2. For a PDA $M$, $L_2(M)$ is the set of all words which can be processed by $M$ in such a way that at the end, $M$ is at an accepting state.

A basic theorem shows that both acceptance criteria are equivalent:

For each language $L$ the following holds: there exists a PDA $M_1$ such that $L_1(M_1) = L$ iff there exists a PDA $M_2$ such that $L_2(M_2) = L$.

A language $L$ is context-free if there exists a PDA $M$ such that $L_1(M) = L$. Equivalently, a language $L$ is context-free if there exists a PDA $M$ such that $L_2(M) = L$. The two definitions are equivalent due to the theorem.

Some PDAs are deterministic – call those DPAs. The basic theorem doesn't hold for DPAs. According to Wikipedia, there exists a DPA $M_1$ such that $L_1(M_1) = L$ iff $L$ is prefix-free (no word is a prefix of another word) and there exists a DPA $M_2$ such that $L_2(M_2) = L$.

A language $L$ is deterministic context-free if there exists a DPA $M$ such that $L_2(M) = L$.

If $L_1(M) = L$ for some DPA $M$ then $L$ is deterministic context-free, but $L$ could be deterministic context-free without there existing a DPA $M$ such that $L_1(M) = L$.