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
