2
$\begingroup$

I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax:

$\delta(q, \lambda, S) = \{(q, aaB), (q, bbA)\}$

This is one of the rules for my language. I am unsure of what the meanings of this syntax exactly is.

|cite|improve this question
$\endgroup$
3
$\begingroup$

The rule, in English, can be rendered roughly as follows:

If the machine is in state $q$, and $S$ is the topmost stack symbol, the machine may do either of the following things without consuming any input: it may remain in state $q$ and replace $S$ with $aaB$; or it may remain in $q$ and replace $S$ with $bbA$.

A good way to think about PDAs and transitions is to reason about configurations. The configuration of a PDA consists of the following information: the state, the unread input, and the contents of the stack. Indeed, this makes the transition function (almost) a (partial) function from configurations to (sets of) configurations.

  • $q$ is the state;
  • $\lambda$ is used to indicate that the current symbol may be input symbol, and that the input should not be reduced as it normally would after a transition;
  • $S$ gives the topmost stack symbol, which is the only part of the stack contents the PDA can see.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ so if the $\lambda$ was something else, like an a, it would mean that the input symbol read is an a? Also, what does the pairs on the right side of the = sign mean as well? $\endgroup$ – Matt Hintzke Apr 9 '13 at 21:53
  • $\begingroup$ @MattHintzke (1) Correct, an $a$ would mean that the first symbol of the remaining input must be $a$ for the transition to apply and, if the transition is taken, then this $a$ is consumed, reducing the number of remaining input symbols. $\endgroup$ – Patrick87 Apr 9 '13 at 22:26
  • 2
    $\begingroup$ @MattHintzke (2) The pairs on the right give the state and changes to stack contents of the new configuration of the PDA after that transition is taken. When multiple pairs are given, multiple transitions are possible, and one would be chosen nondeterministically. The first member of each pair is the new state; the second is the string of symbols to replace the top stack symbol with. $\endgroup$ – Patrick87 Apr 9 '13 at 22:26
  • $\begingroup$ I'd like to add that whether the first or last symbol of $aaB$ resp. $bbA$ ends up on top of the stack depends on the definition at hand, and is vital. $\endgroup$ – Raphael♦ Apr 10 '13 at 8:43

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.