Push down automata what to do when there is no suitable transition

Question

This is a question that has emerged from a recent quiz I have taken. In short

Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the following inputs will lead the automaton to state p with the stack containing the string XXZ?

I am gonna write only the transitions from state q regardless of the input symbol:

 (q, 0, Z) -> (q, XZ)
 (q, 0, X) -> (q, XX)
 (q, 1, X) -> (q, X)
 (q, ε, Χ) -> (p, ε)

Now the thing we note here is that there is no transition from state q when there is an empty stack regardless of the input symbol. How does one answer that question assuming we start from an empty stack? I have omitted the inputs cause I don't really care about the answer to the quiz, all I want to know is how would someone start working on that?

Answer 1

Starting with empty stack is not allowed.

A PDA is usually defined as (Q, Σ, Γ, δ, q0, Z0, F), where the symbols have their usual meanings. One of these is Z0, the stack start symbol. It is on the stack when the PDA starts.

So by definition you have Z0 on the stack at start. You need to find Z0 in your case and start with that.

Answer 2

Given the form of transitions, they cannot be applied when the stack is empty, since there is then no symbol to be read from it. Hence you cannot assume that you start with an empty stack: it would make no sense.

Actually the definition you use, that of wikipedia page on pushdown automata, uses $Z$ as initial stack symbol. Hence you should assume that at the beginning your stack contains $Z$ at its bottom.

Then any string from the regular set $0001^*(0+1)$, for example $0001110$, can produce the desired result (non deterministically), i.e. being in state $p$ with XXZ on the pushdown stack. The fourth transition should be used last.