3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is your statement? $\endgroup$ – Auberon May 16 '16 at 21:06
  • $\begingroup$ @Auberon I hope it's clear now. $\endgroup$ – C. White May 16 '16 at 21:09
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I'd to like to add that both conditions may be used in a PDA and that a PDA may push/pop multiple symbols to/from the stack. $\endgroup$ – Auberon May 16 '16 at 21:20
  • $\begingroup$ Accepting "at the end" can be confusing terminology: the PDA might do some epsilon-moves before accepting after having read the complete input. $\endgroup$ – Hendrik Jan May 17 '16 at 0:06

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.