# Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

PDA = Pushdown Automata

Let's assume I have this language:

$L = \{a^nb^ma^n | m,n \ge 1\}$

Would the first approach with one node be enough - in that case it guess twice the $\lambda$. In the second approach it's deterministic, which is fine.

• What a PDA can do is defined by the syntax and semantics of PDAs. If you understand the syntax of PDAs - how a PDA is defined - and its semantics - what is the language that the PDA accepts - then you already know what a PDA can and cannot do. – Yuval Filmus Feb 27 '18 at 8:53
• @YuvalFilmus After reading more than once the definitions, and solving many exercises, checking solutions, this is the first time I've approached a solution that makes the PDA guess twice. Maybe I didn't understand the solution, or the definition. – Ilan Aizelman WS Feb 27 '18 at 8:55
• You can do everything which is allowed by the rules. In mathematics we have complete freedom under the rules of the game. – Yuval Filmus Feb 27 '18 at 9:14
• @YuvalFilmus From my understanding of the definitions, the non-deterministic approach says "if we have at least one solution", we accept it and finish. But Meaning at every step of the way it can guess whether to guess or not. – Ilan Aizelman WS Feb 27 '18 at 9:18
• That's up to the syntax of the specific PDA model you're using, but generally speaking it's a reasonable shortcut. – Yuval Filmus Feb 27 '18 at 13:23