$ \sigma $ and the stack-top symbol is $ \gamma $, then it moves to the state $ s' $ and updates the stack by deleting the stack-top symbol and pushing $ \bar{\gamma'} $. Also, the tape head moves to $D$ where $ D=0 $ means “stationary” and $ D=1 $ means “move to the right”. Note that a move with $ D=0 $ is called an $\varepsilon$-move. For an input word $ w $, if $ A $ reaches an accepting state, then $ w $ is accepted.

A promise problem ${\tt P} \subseteq \Sigma^* $ is formed by two disjoint subsets: yes-instances $ \tt P_{yes} $ and no-instances $ \tt P_{no} $. An automaton $ A $ solves $ P $ with error bound $ \epsilon < \frac{1}{2} $ if each yes-instance (resp. no-instance) is accepted (resp. rejected) with probability at least $ 1 - \epsilon $. If all yes-instances (resp. no-instances) are accepted with probability 1 (resp. 0), then the error bound is called one-sided. If $ \epsilon = 0 $, then the problem is said to be solved exactly (or with zero-error). A promise problem is solved by a Las Vegas algorithm with success probability $ 