Existence of one and two state PDAs

Question

I came across following fact in Automata book by Hopcroft, Ullman:

Theorem 1: For every PDA accepting by empty stack (PDAeS), there is an equivalent one state PDA accepting by empty stack.

I was wondering how this applies to:

1. PDA accepting by final state (PDAfS)
2. Deterministic PDA accepting by empty stack (DPDAeS)
3. Deterministic PDA accepting by final state (DPDAfS)

My understanding is, it applies equally to PDAfS, since I read in the book that both PDAfS and PDAeS are of equal power. Am I right? Also what about DPDAs?

Also I came across this post, which states:

Theorem 2: All PDAs are equivalent to two state PDAs.

I want to know what all variants (PDAfS, PDAeS, DPDAeS, DPDAfS) it refers to by PDA? Reading the explanation given in the problem itself, my guess is that it is possible with PDAeS and DPDeS. Am I right?

Added later

I came across two more theorems in the book:

Theorem 3: For every regular language L, there is DPDAfS, such that L = L(DPDAfS) Theorem 4: For every regular language L, there is one state PDAeS, such that L = L(PDAeS)

So in all above highlighted theorems (total four, two originally stated and two added later), I want to know to what they apply? PDAeS, PDAfS, DPDAeS, DPDAfS.

So let me enumerate problems explicitly:

(From theorem 1)

1. For every PDA, is there equivalent one state PDAfS?
2. For every DPDA, is there equivalent one state DPDAeS?
3. For every DPDA, is there equivalent one state DPDAfS?

(From theorem 2)

4. Is all PDAs are equivalent to some two state PDAeS?
5. Is all PDAs are equivalent to some two state PDAfS?

(From theorem 3)

6. For every regular language L, is there DPDAeS, such that L = L(DPDAeS)? (details in Update 1)

(From theorem 4)

7. For every regular language L, is there one state PDAfS, such that L = L(PDAfS)?

Update 1

Realized that the answer to 6th question is no. DPDAeS are not even capable of generating all regular languages. This leads to the possible next question:

8. Cant any DPDAeS generate any regular language?

PS:

• Sorry, if you didnt like how I am referring to PDAs with fS and eS suffixes (which mean "acceptance by final state" and "acceptance by empty state" respectively). But I find it very convenient.
• Sorry for asking absolutely too much on one post. But all those problems form a part of one big problem: how FAs, PDAeS, PDAfS, DPDAeS, DPDAfS and their variants (one state and two state) generate each other.

Answer 1

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.

Answer 2

Every PDA is equivalent to a PDAeS with a single state. This is because every context-free grammar can be simulated by such a PDAeS (nice exercise). This PDAeS, in turn, is equivalent to a PDAfS with two states.

I'm not sure whether the same reduction works for DPDAs – perhaps.