0
$\begingroup$

I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states?

For example,

 - if you have a 1 and the stack is empty, push it on the stack, and transition to q1
 - if you have a 0 and the stack is empty, push it on the stack, and transition to q1
 - if you have a 1 and there is a 1 on the stack, push it on the stack, and transition to q1
 - if you have a 1 and there is a 0 on the stack, pop the 0 off, and transition to q1
 - if you have a 0 and there is a 0 or 1 on the stack, push it on the stack and stay in q0

I was wondering if this is allowed, and it knows what to do given the scenario?

Sorry if this is obvious, I have been looking at some PDAs and haven't seen any that have multiple options to transition between states and was wondering if it was allowed.

$\endgroup$
2
$\begingroup$

Simple answer: yes, that is allowed. In the example you give, it's simple--depending on the input symbol and the stack contents, there's one and only one choice for the action of the machine in state $q_0$. It's even possible to have several actions as consequence to a single (input, stack top) pair, like this,

-- input 0 and stack top 1, push 0 and go to state $q_2$

-- input 0 and stack top 1, push 1 and go to state $q_3$

Seems wierd, I know but such machines are called nondeterministic pushdown automata and are quite useful; look them up.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer! While doing a google search, nondeterministic pushdown automata seem synonymous with push down automata, or is there a difference? $\endgroup$ – DoubleRainbowZ Oct 14 '19 at 0:38
  • $\begingroup$ It's more or less a personal preference of the author. Since nondeterministic pushdown automata (NPDAs) include the deterministic kind (DPDAs), some people simply use the most inclusive definition and leave it at that. By the way, welcome to the site! $\endgroup$ – Rick Decker Oct 14 '19 at 23:37
  • $\begingroup$ Ah ok, I see! Thanks :) $\endgroup$ – DoubleRainbowZ Oct 15 '19 at 2:17

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.