$ is a finite set of states, $ \Sigma $ is a finite set of input symbols, $ \Gamma $ is a finite set of stack symbols, $ \delta : S\times \tilde{\Sigma} \times \Gamma \times S \times \Gamma^* \times \{0,1\} \longrightarrow \{0,1\} $ is a transition function, $ s_I $ is the initial state, $ Z_0 $ is the initial stack symbol, and $ S_a\subseteq S $ is the set of accepting states. To be a well-formed machine, the transition function must satisfy that, for each triple $ (s, \sigma, \gamma) $, $$\sum_{s'\in S, \gamma'\in \Gamma^*, D\in\{0,1\}} \delta(s, \sigma, \gamma, s', \gamma', D) = 1.$$

For a given input $ {\mbox{\textcent}}w {\$}$, the automaton $ A $ starts its computation with the following initial configuration:

-   the initial state is $ s_I $,

-   the stack has only the initial stack symbol $ Z_0 $,

-   the tape head points to the left endmarker.

Then, at each step of the computation, $ A $ is updated according to the transition function $ \delta $, i.e., $ \delta(s, \sigma, \allowbreak \gamma,  s', \bar{\gamma'}, D) =1 $ implies that if the current state is $ s $, the scanned input symbol is 