[Solved]: Syntax of a Pushdown Automata transition function

Problem Detail: 

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.

Asked By : Matt Hintzke

Answered By : Patrick87

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.

Best Answer from StackOverflow

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