0
$\begingroup$

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

$\endgroup$
  • 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$ – Yuval Filmus Feb 27 '18 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$ – Ilan Aizelman WS Feb 27 '18 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$ – Yuval Filmus Feb 27 '18 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$ – Ilan Aizelman WS Feb 27 '18 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$ – Yuval Filmus Feb 27 '18 at 13:23
0
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ I've already posted a solution. I've asked something else in the thread. But thanks for the input. $\endgroup$ – Ilan Aizelman WS Feb 27 '18 at 9:19
  • $\begingroup$ The image did not load :p. $\endgroup$ – Sagnik Feb 27 '18 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.