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.enter image description here

  • 1
    $\begingroup$ 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. $\endgroup$ Feb 27, 2018 at 8:53
  • $\begingroup$ @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. $\endgroup$ Feb 27, 2018 at 8:55
  • 2
    $\begingroup$ You can do everything which is allowed by the rules. In mathematics we have complete freedom under the rules of the game. $\endgroup$ Feb 27, 2018 at 9:14
  • $\begingroup$ @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. $\endgroup$ Feb 27, 2018 at 9:18
  • 1
    $\begingroup$ That's up to the syntax of the specific PDA model you're using, but generally speaking it's a reasonable shortcut. $\endgroup$ Feb 27, 2018 at 13:23

1 Answer 1


Here is a solution with one stack.

  1. Start inserting a's into the stack.
  2. Stop inserting a's when we encounter the first b. Halt any operations with respect to the stack as long as we get b's.
  3. Start popping stack contents immediately when the b's stop and a's start.
  • $\begingroup$ I've already posted a solution. I've asked something else in the thread. But thanks for the input. $\endgroup$ Feb 27, 2018 at 9:19
  • $\begingroup$ The image did not load :p. $\endgroup$
    – Sagnik
    Feb 27, 2018 at 9:22

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.