Skip to main content
1 of 2
zpavlinovic
  • 1.7k
  • 10
  • 19

As you can see, $\Delta$ is a set of pairs that encode 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 $(q, \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), (q, \gamma))$ as

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

zpavlinovic
  • 1.7k
  • 10
  • 19