# PDA with more than one initial state

I'm wondering if PDAs with more than one initial states are also accepting context free languages.

If found that question on this site about NFAs and would like to know if this answer is also valid for PDAs if one defines a new single initial state and connects this with the former initial states using $$\epsilon : \epsilon \to \epsilon$$ transitions?

## 2 Answers

PDAs that are allowed to have more than one initial state (let's call them PDAIs) are computationally equivalent to conventional PDAs:

• Trivially, every conventional PDA can be considered as a PDAI that happens to have one initial state.
• Every PDAI can be converted to an equivalent PDA with the process you describe.

So yes, PDAIs accept exactly the context free languages.

Yes this is possible. In fact, if we take out the non-determinism from the PDAs, then we end up with something that is computationally significantly weaker!