# Existence of one and two state PDAs

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?

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)

1. Is all PDAs are equivalent to some two state PDAeS?
2. Is all PDAs are equivalent to some two state PDAfS?

(From theorem 3)

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

(From theorem 4)

1. 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:

1. 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.
• "I was wondering how this applies to:" -- If the theorem says, "for every apple, ..." then it says something about apples and apples only. No use in wondering if it applies to oranges. Or are you asking whether a similar theorem holds for oranges? – Raphael Dec 8 '17 at 16:09
• Yes of course I was asking if similar theorem holds for oranges. Just in case oranges slipped from author's attention and author forgot to explicitly say something similar about the oranges...Though its unlikely for such a good author...my bad... – anir Dec 8 '17 at 16:26
• It's always good to be curious and critical about what you read, no matter who wrote it! Even the best authors make mistakes. Just wanted to make sure you were not asking a fallacious question. – Raphael Dec 10 '17 at 17:32
• Your "e" and "f" suffixes are quite OK. I personally do not like to extend them to "eS" and "fS" as "S" might mean both "[empty] stack" and "[final] state". – Hendrik Jan Dec 12 '17 at 14:06

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.

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.

• just to confirm, are you sure if your first sentence is correct. 2nd edition of Hopcroft, Ullman book specifically says what I stated in 1st theorem in its exercise 6.3.6: "Show that if $P$ is a PDA, then there is a one-state PDA $P_1$, such that $N(P_1)=N(P)$". To be specific, its not "Every PDA", but "Every PDAeS" – anir Dec 8 '17 at 13:52
• If you want to be sure, I suggest you try proving the statement yourself. – Yuval Filmus Dec 8 '17 at 13:55
• @anir The grammar doesn't care what the automaton it was generated from looked like. – Raphael Dec 8 '17 at 16:08