0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.