0
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 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. ♦
    Commented Nov 21, 2013 at 17:02

1 Answer 1

Reset to default
1
$\begingroup$

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)$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.