If you want to make money online : Register now

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

, , No Comments
Problem Detail: 

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?

Asked By : Theocharis K.

Answered By : Computer

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44084

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback