I know how to figure out the start state, accepting state, input alphabet, and all that stuff. But how do you develop the transition relation of a PDA? For an FSM, (q0,a),q1) means if you start at q0 and get an a, you transition to q1. But what does (S,a,e),(S,a) mean? (S is start state and e is epsilon)

Here's a picture if that helps. I want to understand the circled part. I will be extremely appreciative of any help.
enter image description here

  • 1
    $\begingroup$ I'm not sure what you're asking. At one part, you ask what $(S,a,\epsilon),(S,a)$ means -- is that what you want to know? If so, what research/self-study have you done, and where exactly did you get stuck? Have you read your textbook's chapter on PDA's? Have you read Wikipedia's article on PDAs? It even has a sentence that describes what this means, starting with the phrase "It has the intended meaning that...." Alternatively, if that isn't what you meant to ask, I think you should edit the question to make things clearer. $\endgroup$
    – D.W.
    Nov 21 '13 at 17:02

As you can see, $\Delta$ is a set of pairs that represent a transition function. First element of the pair is a triple $(q, a, X)$, where $q$ is a state, $a$ is an input symbol (possibly empty string), and $X$ is the top stack symbol.

The other element of the pair describes the action of PDA when its configuration fits the above triple. This other element is again a pair $(p, \gamma)$, where $p$ is a new state and $\gamma$ is a sequence of symbols replacing $X$. If $\gamma = \epsilon$, then $X$ is just popped.

It might help to view $((q, a, X), (p, \gamma))$ as

$$(q, a, X) \rightarrow (p, \gamma)$$


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.