Skip to main content
2 of 2
added how my observations actually answered the questions
Hendrik Jan
  • 31.1k
  • 1
  • 54
  • 107

For final state acceptance one needs two states in general. The reason is simply that one needs to distinguish accepted and not-accepted strings. That is why single state PDAf are not a very useful concept. But if you have one, the prefix of every accepted string will itself be also accepted. These languages are prefix-closed.

If a deterministic automaton with empty stack acceptance indeed accepts a string, there is no longer string that can be accepted. The reason is that with empty stack in the classical model of Hopcroft&Ullman the automaton blocks, no steps are possible. Here determinism is important because nondeterministic automata just may have alternative computations on the same string. These languages are prefix-free.

Let me summarize.

The answer to question 1, question 3 and question 7 [single state with final state acceptance] is "no" as not every (D)PDA language is prefix closed, for example regular $(aa)^*$, or in fact finite $\{a,aa\}$.

The answer to question 2 [single state, deterministic, empty stack] is "no", as not every DPDA language is prefix-free, examples as before.

The answer to question 4 and question 5 [two states] are "yes", see Yuval's answer. These results are 'classic'. Perhaps you want to know the deterministic version of these results?

For question 8 observe that DPDAe's can accept 'any' regular language when the end of the string is marked by a special symbol. This makes the language immediately prefix-free.

Hendrik Jan
  • 31.1k
  • 1
  • 54
  • 107