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:
- PDA accepting by final state (PDAfS)
- Deterministic PDA accepting by empty stack (DPDAeS)
- 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)
- For every PDA, is there equivalent one state PDAfS?
- For every DPDA, is there equivalent one state DPDAeS?
- For every DPDA, is there equivalent one state DPDAfS?
(From theorem 2)
- Is all PDAs are equivalent to some two state PDAeS?
- Is all PDAs are equivalent to some two state PDAfS?
(From theorem 3)
For every regular language L, is there DPDAeS, such that L = L(DPDAeS)?(details in Update 1)
(From theorem 4)
- For every regular language L, is there one state PDAfS, such that L = L(PDAfS)?
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:
- Cant any DPDAeS generate any regular language?
- 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.