0
$\begingroup$

Suppose we're given the non-deterministic PDA shown below which reads from the alphabet $\sum = \lbrace a,b \rbrace$. How will this PDA behave if we pass it the string $ba$? We read $b$ first and push $b$ to the stack, but when we read $a$ I get confused. My assumption is that we fork into two new branches - one in which $b$ was popped and one in which $a$ was pushed. Is this correct? If not, can you tell me where I go wrong?

Thank you very much!

enter image description here

$\endgroup$
  • $\begingroup$ You're correct. $\endgroup$ – Rick Decker Feb 27 at 15:57
0
$\begingroup$

This PDA is non deterministic. So just like in non-deterministic Finite State Machines you fork.

A string is only accepted by the PDA if one of the forks ends in an accepting state.

$\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.