# 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. Feb 27, 2018 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. Feb 27, 2018 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. Feb 27, 2018 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. Feb 27, 2018 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. Feb 27, 2018 at 13:23