0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to SE Computer Science. Is this all the information you have. If the quiz was in the context of a course, what definition of PDA have you been using? What is supposed to be the initial state and initial stack content? $\endgroup$ – babou Jul 1 '15 at 16:11
  • $\begingroup$ @babou I have some other transitions from state p which are irrelevant and 4 possible inputs. One of them is correct, I am asked to find which one. The definition of the PDA we are using is the same as the formal one in the push down automata wiki page, minus the Z symbol. We don't use a symbol to indicate where the stack ends, instead it ends in the final symbol. The exercise itself states that Z in the string is the lower bound of the stack. As I have mentioned the initial state is q and nothing is given about the stack soI assume it's empty $\endgroup$ – Theocharis K. Jul 1 '15 at 16:18
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You were right. The z0 in my case was simply Z. Thanks. $\endgroup$ – Theocharis K. Jul 3 '15 at 12:09
1
$\begingroup$

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.

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