  In various models of one-way pushdown automata, the explicit use of two
designated endmarkers on a read-once input tape has proven to be extremely
useful for making a conscious, final decision on the acceptance/rejection of
each input word right after reading the right endmarker. With no endmarkers, by
contrast, a machine must constantly stay in either accepting or rejecting
states at any moment since it never notices the end of the input instance. This
situation, however, helps us analyze the behavior of the machine whose tape
head makes the consecutive moves on all prefixes of a given extremely long
input word. Since those two machine formulations have their own advantages, it
is natural to ask whether the endmarkers are truly necessary to correctly
recognize languages. In the deterministic and nondeterministic models, it is
well-known that the endmarkers are removable without changing the acceptance
criteria of each input instance. This paper proves that, for a more general
model of one-way probabilistic pushdown automata, the endmarkers are also
removable. This is proven by employing probabilistic transformations from an
"endmarker" machine to an equivalent "no-endmarker" machine at the cost of
double exponential state complexity without compromising its error probability.
By setting this error probability appropriately, our proof also provides an
alternative proof to both the deterministic and the nondeterministic models as
well.

Formal Languages and Automata Theory;Computational Complexity