Does a PDA follow a transition if the top stack symbol doesn't match?

Question

Does a PDA only move states when both the input symbol matches and the symbol on the top of the stack matches?

In other words, is it possible to have two different transitions that both take the same input character but pop different stack symbols?

For example if we have a state Q0 with the two following transitions:

a, a -> b a, b -> a

I know that a PDA will transition in regards to the input symbol but how does it handle the stack symbol that it is trying to pop?

For some reason I can not find the answer to this simple question for the life of me. I have searched and searched in my textbook and online.

Answer 1

TL;DR: No, it does not.

I would guess that your notation a, a -> b means the syntax in a PDA transition such that if we read a character a from the input and we pop a character a from the stack, then we put a character b on top of the stack.

The notation of that transition that I'm used of is written as $$q\xrightarrow{\text{e,d;u}}r,$$

where the left side of the semicolon is what we read, i.e. character e from the input and character (or symbol) d from the stack. Right side of the semicolon is what we put onto the stack: u.

In order for your PDA to follow a transition, it has to match both of the conditions on the left side of the above notation. So, your PDA won't follow that particular transition if the stack symbol doesn't match.

What comes to your second question about having two different transitions with same input but different stack symbol, yes, that is possible based on nondeterminism, but your PDA still has to meet both conditions in the left side of the notation in order to move anywhere.

Hope this had any help!

Answer 2

No to the title, Yes to the question in the description. The domain of the transition function $\delta$ of the PDA is given by $$Q\times (\Sigma\cup\{\epsilon\})\times(\Gamma\cup\{\epsilon\})$$

The input of the PDA is thus a 3-tuple $(q,a,b)$, where $q\in Q, a\in\Sigma\cup\{\epsilon\}, b\in\Gamma\cup\{\epsilon\}$.

If the character at the top of the stack is different, the input to the transition function is different, and it can give different outputs in each case. You can have, as per your example, something like

$$\delta(q_0,a,a)=(q,b)$$ $$\delta(q_0,a,b)=(q,a)$$

where $q_0,q\in Q$ and $a,b \in \Sigma$ and $a,b\in \Gamma$.

Such examples are often found in the transition functions, such as in this example.

The transition is not with regards to just the input symbol, it depends on all the three values, the state, the input symbol, and the symbol on the top of the stack, which form the input.