The No Endmarker Theorem for One-Way Probabilistic Pushdown Automata

Tomoyuki Yamakami111Current Affiliation: Faculty of Engineering, University of
Fukui, 3-9-1 Bunkyo, Fukui 910-8507, Japan

###### Abstract

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.

Keywords. probabilistic pushdown automata, endmarker, descriptional
complexity, acceptance criteria, stack-state complexity

##  1 With or Without Endmarkers, That is a Question

###  1.1 Two Different Formulations of One-Way Pushdown Automata

In automata theory, _pushdown automata_ are regarded as one of the most
fundamental architectures operated with finite-state controls. A pushdown
automaton is, in general, a finite-controlled machine equipped with a special
memory device, called a _stack_ , in which information is stored and accessed
in the first-in last-out manner. Here, we are focused on one-way pushdown
automata whose tape heads either move to the right or stay still at any step.
In particular, a nondeterministic variant of those machines, known as _one-way
nondeterministic pushdown automata_ (or 1npda’s), characterizes context-free
languages. Similarly, _one-way deterministic pushdown automata_ (or 1dpda’s)
introduce deterministic context-free languages. These machines can be seen as
special cases of a much general model of _one-way probabilistic pushdown
automata_ (or 1ppda’s). Macarie and Ogihara [8] discussed the computational
complexity of languages recognized by 1ppda’s with unbounded-error
probability. In recent literature, Hromkovič and Schnitger [4] and Yamakami
[15] further discussed the limitations of the power of bounded-error 1ppda’s.

In textbooks and scientific papers, ignoring small variational deviations,
various one-way pushdown automata have two distinct but widely-used
formulations. At the first glance, those formulations look quite different and
it is not obvious that they are essentially “equivalent” in recognition power.
In the first formalism, an input string over a fixed alphabet is initially
given to an input tape together with two designated endmarkers, which mark
both ends of the input string. The machine starts at scanning the left
endmarker ${|}\\!\\!\mathrm{c}$ and moves its tape head to the right whenever
it accesses an input symbol until it reaches the right endmarker $\$$. In
addition, the machine can proceed without reading any input symbol even after
reading $\$$. Such special steps are called _$\lambda$ -moves_ or a _$\lambda$
-transitions_. Even if the machine halts even before reading the endmarker by
entering halting states, the use of $\lambda$-moves makes it possible to
postpone the time to halt until the machine reads the right endmarker.
Whenever the machine enters a halting state (i.e., either an accepting state
or a rejecting state), the machine is considered to halt and its computation
terminates in acceptance or rejection depending on the type of halting states.

In the second formalism, by sharp contrast, the input tape contains only a
given input string without the presence of two endmarkers and the machine
starts reading the input from left to right until it reads off the rightmost
symbol. Since the machine need to access the entire input string without
knowing the end of the input, whenever the machine reads off the input, it is
considered to “halt” and the current inner state of the machine determines the
acceptance and rejection of the input.

For convenience, we call a model described by the first formalism an
_endmarker model_ and one by the second formalism a _no-endmarker model_.
Kaņeps, Geidmanis, and Freivalds [6], Hromkovič and Schnitger [4], and
Yamakami [15] all used a no-endmarker model of 1ppda’s (succinctly called _no-
endmarker 1ppda’s_) in their analyses of machine’s behaviors, whereas an
endmarker model of 1ppda’s (called _endmarker 1ppda’s_) was used by Macarie
and Ogihara [8] and Yamakami [16]. It is commonly assumed that endmarker
1ppda’s are equivalent in recognition power to no-endmarker 1ppda’s.
Unfortunately, there is no “formal” proof for the equivalence between those
two models _without compromising error probability_.

The roles of two endmarkers, the left and the right endmarkers, are clear. In
the presence of the right endmarker $\$$, in particular, when the machine
reads $\$$, the machine certainly notices the end of the input string and,
based on this knowledge, it can make the final transition (followed by a
possible series of $\lambda$-moves) before entering either accepting or
rejecting states. In the presence of $\$$, we can make a series of
$\lambda$-moves to empty the stack before halting. Without the right
endmarker, however, the machine must be always in a “constantly halting” inner
state (either an accepting state or a rejecting state). Such an inner state
determines the acceptance or rejection of an input just after reading off the
entire input string and possibly following a series of $\lambda$-moves.

This halting condition certainly helps us analyze the behavior of the machine
simply by tracing down the changes of accepting and rejecting states on all
prefixes of any extremely long input string. For instance, some of the results
of Hromkovič and Schnitger [4] and Yamakami [15] were proven in this way.

For 1dpda’s as well as 1npda’s, Hopcroft and Ullman [3] used in their textbook
the no-endmarker model to define pushdown automata whereas Lewis and
Papadimitriou [7] suggested in their textbook the use of the endmarker model.
For those basic pushdown automata, the endmarker model and the no-endmarker
model are in fact well-known to be “equivalent” in their computational power.
We succinctly call this assertion the _no endmarker theorem_ throughout this
paper.

For 1npda’s, for instance, we can easily convert one model to the other
without compromising its acceptance/rejection criteria by first transforming a
1npda $M$ to its equivalent context-free grammar, converting it to Greibach
Normal Form, and then translating it back to its equivalent 1npda (see, e.g.,
[3]).

The question of whether the endmarker models of one-way pushdown automata can
be computationally equivalent to the no endmarker models of the same machine
types is so fundamental and also useful in the study of various types of one-
way pushdown automata. This paper extends our attention to 1ppda’s—a
probabilistic variant of pushdown automata. For such 1ppda’s, we wish to argue
whether the no endmarker theorem is indeed true because, unfortunately, not
all types of pushdown automata enjoy the no endmarker theorem. The right
endmarker can be eliminated if our machine model is closed under right
quotient with regular languages (see, e.g., [3]). Since 1dpda’s and 1npda’s
satisfy such a closure property [2], the no endmarker theorem holds for those
machine models. For counter machines (i.e., pushdown automata with single
letter stack alphabets except for the bottom marker), on the contrary, the
endmarkers are generally unremovable [1]; more precisely, the deterministic
reverse-bounded multi-counter machines with endmarkers are generally more
powerful than the same machines with no endmarkers. This latter fact
demonstrates the crucial role of the endmarkers for pushdown automata. It is
therefore significantly important to discuss the removability of the
endmarkers for bounded-error and unbounded-error 1ppda’s.

###  1.2 The No Endmarker Theorem

This paper presents the proof of the _no endmarker theorem_ for 1ppda’s with
arbitrary error probability. More precisely, we prove the following statement,
which allows us to safely remove the two endmarkers of 1ppda’s without
compromising error probability.

###### Theorem 1.1

[No Endmarker Theorem] Let $\Sigma$ be any alphabet and let
$\varepsilon:\Sigma^{*}\to[0,1/2)$ be any error-bound parameter (when
$\varepsilon(x)$ is a one-sided error, we can take $\varepsilon(x)\in[0,1)$
instead). For any language $L$ over $\Sigma$, the following two statements are
logically equivalent.

  1. 1.

There exists a 1ppda with two endmarkers that recognizes $L$ with error
probability $\varepsilon(x)$ on every input $x$.

  2. 2.

There exists a 1ppda with no endmarker that recognizes $L$ with error
probability $\varepsilon(x)$ on every input $x$.

The first part of Theorem 1.1 for 1ppda’s asserts that we can safely eliminate
the two endmarkers from each 1ppda without changing the original error
probability. The invariance of this error probability is important because
this invariance makes it possible to apply the same proof of ours to both
1dpda’s and 1npda’s as special cases by setting $\varepsilon(x)=0$ for all
$x\in\Sigma^{*}$ and by making $\varepsilon(x)=0$ for all $x\in L$ and
$\varepsilon(x)<1$ for all $x\in\overline{L}$, respectively. Thus, we obtain
the well-known fact that the endmarkers are removable for 1dpda’s and 1npda’s.

###### Corollary 1.2

Theorem 1.1 also holds for 1dpda’s as well as 1npda’s.

Since the proof of Theorem 1.1 is constructive, it is possible to discuss the
increase of the number of inner states and of stack alphabet size in the
construction of new machines. Another important factor is the maximal size of
stack strings stored by “push” operations. We call this number the _push size_
of the machine. Throughout this paper, altogether of those three factors are
succinctly referred to as the _stack-state complexity_ of transforming one
model to the other.

For brevity, we say that two 1ppda’s (with or without endmarkers) are _error-
equivalent_ if their outputs agree with each other on all inputs with exactly
the same error probability.

###### Proposition 1.3

Given an $n$-state no-endmarker 1ppda with stack alphabet size $m$ and push
size $e$, there is an error-equivalent endmarker 1ppda of stack alphabet size
$m+2$ and push size $e$ with at most $2n+1$ states.

###### Proposition 1.4

Given an $n$-state endmarker 1ppda with arbitrary push size, there is an
error-equivalent no-endmarker 1ppda such that it is double-exponential in
state size and stack alphabet size but is of push size $1$.

Since Theorem 1.1 follows directly from Propositions 1.3–1.4, we will
concentrate our efforts on proving these propositions in the rest of this
paper. From the propositions, we can observe that endmarker 1ppda’s are likely
to be double-exponentially more succinct in descriptional complexity than no-
endmarker 1ppda’s. We are not sure, however, that this bound can be
significantly improved.

#### Organization of This Paper.

In Section 2, we will start with the formal definition of 1ppda’s (and their
variants, 1dpda’s and 1npda’s) with or without endmarkers. In Section 3, we
will prove Proposition 1.3. Proposition 1.4 will be proven in Section 5. To
simplify the proof of Proposition 1.4 in Section 4, we will transform each
standard 1ppda into another special 1ppda that does not halt before the right
endmarker and takes a “push-pop-controlled” form, called an _ideal shape_ ,
which turns out to be quite useful in proving various properties of languages.
As a concrete example of usefulness, we will demonstrate in Section 4.3 the
closure property of language families induced by bounded-error endmarker
1ppda’s under “reversal”. Lastly, a few open questions regarding the subjects
of this paper will be discussed in Section 6.

##  2 Various One-Way Pushdown Automata

Let us review two machine models of 1ppda’s in details, focusing on the use of
the two endmarkers. A _one-way probabilistic pushdown automaton_ (abbreviated
as 1ppda) $M$ runs essentially in a way similar to a one-way nondeterministic
pushdown automaton (or a 1npda) except that, instead of making a
nondeterministic choice at each step forming a number of computation paths,
$M$ randomly chooses one of all possible transitions and then branches out to
produce multiple computation paths. The probability of such a computation path
is determined by a series of random choices made along the computation path.
The past literature has taken two different formulations of 1ppda’s, _with_ or
_without_ two endmarkers. We will explain these two formulations in the
subsequent subsections.

###  2.1 Numbers, Strings, and Languages

Let $\mathbb{N}$ denote the set of all _natural numbers_ , including $0$, and
set $\mathbb{N}^{+}$ to be $\mathbb{N}-\\{0\\}$. Given a number
$n\in\mathbb{N}^{+}$, $[n]$ denotes the set $\\{1,2,\ldots,n\\}$. Given a set
$A$, ${\cal P}(A)$ denotes the _power set_ of $A$; namely, the set of all
subsets of $A$.

An _alphabet_ is a finite nonempty set of “letters” or “symbols.” Given an
alphabet $\Sigma$, a _string_ over $\Sigma$ is a finite sequence of symbols in
$\Sigma$. Conventionally, we use $\lambda$ to express the _empty string_ as
well as the pop operant for a stack. The _length_ of a string $x$, expressed
as $|x|$, is the total number of symbols in $x$. For a string
$x=x_{1}x_{2}\cdots x_{n-1}x_{n}$ over $\Sigma$ with $x_{i}\in\Sigma$ for any
index $i\in[n]$, the _reverse_ of $x$ is the string $x_{n}x_{n-1}\cdots
x_{2}x_{1}$ and is denoted by $x^{R}$.

The notation $\Sigma^{*}$ indicates the set of all strings over $\Sigma$
whereas $\Sigma^{+}$ expresses $\Sigma^{*}-\\{\lambda\\}$. A _language_ over
$\Sigma$ is a subset of $\Sigma^{*}$. For two languages $A$ and $B$, $AB$
denotes the _concatenation_ of $A$ and $B$, that is, $\\{xy\mid x\in A,y\in
B\\}$. In particular, when $A=\\{w\\}$, we write $wB$ instead of $\\{w\\}B$.
Similarly, when $B=\\{w\\}$, we use the notation $Aw$. For a number
$k\in\mathbb{N}$, $A^{k}$ expresses the set $\\{x_{1}x_{2}\cdots x_{k}\mid
x_{1},x_{2},\ldots,x_{k}\in A\\}$. Moreover, we use the notation $[A,B]$ for
two sets $A$ and $B$ to denote the set $\\{[a,b]\mid a\in A,b\in B\\}$ of
“bracketed” ordered pairs.

###  2.2 The First Formulation

We start with explaining the first formulation of 1ppda’s whose input tapes
marked by two designated endmarkers. We always assume that those endmarkers
are not included in any input alphabet. As discussed in, e.g., [7], a 1ppda
with two endmarkers (which we call an _endmarker 1ppda_) has a read-once semi-
infinite input tape, on which an input string is initially placed, surrounded
by two endmarkers ${|}\\!\\!\mathrm{c}$ (left endmarker) and $\$$ (right
endmarker). To clarify the use of those two endmarkers, we explicitly include
them in the description of a machine as
$(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$,
where $Q$ is a finite set of inner states, $\Sigma$ is an input alphabet,
$\Gamma$ is a stack alphabet, $\Theta_{\Gamma}$ is a finite subset of
$\Gamma^{*}$ with $\lambda\in\Theta_{\Gamma}$,
$\delta:(Q-Q_{halt})\times\check{\Sigma}_{\lambda}\times\Gamma\times
Q\times\Theta_{\Gamma}\to[0,1]$ (with
$\check{\Sigma}=\Sigma\cup\\{{|}\\!\\!\mathrm{c},\$\\}$ and
$\check{\Sigma}_{\lambda}=\check{\Sigma}\cup\\{\lambda\\}$) is a
_probabilistic transition function_ , $q_{0}\in Q$ is the initial state,
$Z_{0}\in\Gamma$ is the bottom marker, $Q_{acc}\subseteq Q$ is a set of
accepting states, and $Q_{rej}\subseteq Q$ is a set of rejecting states, where
$Q_{halt}$ denotes $Q_{acc}\cup Q_{rej}$. We always assume that $Q_{acc}\cap
Q_{rej}=\varnothing$. For convenience, let $\Gamma^{(-)}=\Gamma-\\{Z_{0}\\}$.
The minimum positive integer $e$ for which
$\Theta_{\Gamma}\subseteq\Gamma^{\leq e}$ is called the _push size_ of $M$.
Each value $\delta(q,\sigma,a,p,u)$ expresses the probability that, when $M$
reads $\sigma$ on the input tape and $a$ in the top of the stack in inner
state $q$, $M$ changes $q$ to another inner state $p$, and replaces $a$ by
$u$. For the clarity reason, we express $\delta(q,\sigma,a,p,u)$ as
$\delta(q,\sigma,a\\!\mid\\!p,u)$, because this emphasizes the circumstance
that $(q,a)$ is changed into $(p,u)$ after scanning $\sigma$.

All tape cells on an input tape are indexed sequentially by natural numbers
from left to right in such a way that ${|}\\!\\!\mathrm{c}$ is located in the
$0$th cell (called the _start cell_), a given input $x$ is placed from cell
$1$ to cell $|x|$, and $\$$ is in the $|x|+1$st cell.

We demand that $Z_{0}$ cannot be removed from the stack; that is, if
$\delta(q,\sigma,a\\!\mid\\!p,u)>0$, then $u\in(\Gamma^{(-)})^{*}$ for any
$a\neq Z_{0}$, and $u\in(\Gamma^{(-)})^{*}Z_{0}$ when $a=Z_{0}$. If
$\sigma=\lambda$, then the tape head must stay still and we call this
transition a _$\lambda$ -move_ (or a _$\lambda$ -transition_); otherwise, the
tape head must move to an adjacent cell. Notice that, unless making a
$\lambda$-move, $M$ always moves its tape head in one direction, from left to
right.

We remark that, in certain literature, a pushdown automaton is assumed to halt
just after reading $\$$ without making any extra $\lambda$-move. For a general
treatment of 1ppda’s, this paper allows the machine to make a (possible)
series of $\lambda$-moves even after reading $\$$ until it finally enters a
halting state. After reading $\$$, the tape head is considered to move off (or
leave) the _input region_ , which is marked as ${|}\\!\\!\mathrm{c}{x}\$$ on
the input tape.

To deal with 1npda’s $\lambda$-moves, for any segment $x$ of input
${|}\\!\\!\mathrm{c}w\$$, we say that _$x$ is completely read_ if $M$ reads
all symbols in $x$, moves its tape head off the string $x$, and makes all
(possible) $\lambda$-moves after reading the last symbol of $x$. At each step,
$M$ probabilistically selects either a $\lambda$-move or a non-$\lambda$-move,
or both. Conveniently, we define $\delta[q,\sigma,a]=\sum_{(p,u)\in
Q\times\Theta_{\Gamma}}\delta(q,\sigma,a\\!\mid\\!p,u)$ for any triplet
$(q,\sigma,a)\in Q\times\check{\Sigma}\times\Gamma$. We demand that $\delta$
satisfies the following _probability requirement_ :
$\delta[q,\sigma,a]+\delta[q,\lambda,a]=1$ for any $(q,\sigma,a)\in
Q\times\check{\Sigma}\times\Gamma$.

To describe the behaviors of a stack, we follow [14] for the basic
terminology. A _stack content_ means a series $z=z_{m}z_{m-1}\cdots
z_{1}z_{0}$ of stack symbols in $\Gamma$, which are stored inside the stack
sequentially from the topmost symbol $z_{m}$ of the stack to the lowest symbol
$z_{0}$ ($=Z_{0}$). Since the bottom marker $Z_{0}$ is not popped, we often
say that the stack is _empty_ if there is no symbol in the stack except for
$Z_{0}$.

A _(surface) configuration_ of $M$ is a triplet $(q,i,w)$, which indicates
that $M$ is in inner state $q$, $M$’s tape head scans the $i$th cell, and
$M$’s stack contains $w$. The _initial configuration_ of $M$ is
$(q_{0},0,Z_{0})$. An _accepting_ (resp., a _rejecting_) _configuration_ is a
configuration with an accepting (resp., a rejecting) state and a _halting
configuration_ is either an accepting or a rejecting configuration. Given a
fixed input $x\in\Sigma^{*}$, we say that a configuration $(p,j,uw)$ _follows_
another configuration $(q,i,aw)$ with probability
$\delta(q,\sigma,a\\!\mid\\!p,u)$ if $\sigma$ is the $i$th symbol of $x$, and
$j=i$ if $\sigma=\lambda$ and $j=i+1$ if $\sigma\neq\lambda$.

A _computation path_ of length $k$ is a series of $k$ configurations, which
describes a history of consecutive “moves” chosen by $M$ on input $x$,
starting at the initial configuration with probability $p_{0}=1$ and, for each
index $i\in[0,k-1]_{\mathbb{Z}}$, the $i+1$st configuration follows the $i$th
configuration with probability $p_{i+1}$, ending at a halting configuration
with probability $p_{k}$. To such a computation path, we assign the
probability $\Pi_{i\in[k]}p_{i}$. A computation path is called _accepting_
(_rejecting_ , resp.) if the path ends with an accepting configuration (a
rejecting configuration, resp.). Generally, a 1ppda may produce an extremely
long computation path or even an infinite computation path; therefore, we must
restrict our attention to finite computation paths.

Hromkovič and Schnitger [4] and Kaņeps, Geidmanis, and Freivalds [6] both used
a model of 1ppda’s whose _computation paths all halt eventually (i.e., in
finitely many steps) on every input_. We also adopt this convention222Even if
we allow infinitely long computation paths with a relative small probability,
we can still simulate two models as in Theorem 1.1, and thus the theorem still
holds. in the rest of this paper. In what follows, we always assume that all
1ppda’s should satisfy this requirement. Standard definitions of 1dpda’s and
1npda’s do not have such a runtime bound, because we can easily convert those
machines to ones that halt within $O(n)$ time (e.g., [3, 12, 14]).

The _acceptance probability_ of $M$ on input $x$ is the sum of all
probabilities of accepting computation paths of $M$ starting with
${|}\\!\\!\mathrm{c}{x}\$$ on its input tape. We express by $p_{M,acc}(x)$ the
acceptance probability of $M$ on $x$. Similarly, we define $p_{M,rej}(x)$ to
be the _rejection probability_ of $M$ on $x$. Whenever $M$ is clear from the
context, we often omit script “$M$” entirely and write, e.g., $p_{acc}(x)$
instead of $p_{M,acc}(x)$. We further say that $M$ _accepts_ (resp.,
_rejects_) $x$ if the acceptance (resp., rejection) probability $p_{M,acc}(x)$
(resp., $p_{M,rej}(x)$) is more than $1/2$ (resp., at least $1/2$). Since all
computation paths are assumed to halt in linear time, for any given string
$x$, either $M$ accepts it or $M$ rejects it. The notation $L(M)$ stands for
the set of all strings $x$ accepted by $M$; that is,
$L(M)=\\{x\in\Sigma^{*}\mid p_{M,acc}(x)>1/2\\}$.

Given a language $L$, we say that $M$ _recognizes_ $L$ if $L$ coincides with
the set $L(M)$. A 1ppda $M$ is said to make _bounded error_ if there exists a
constant $\varepsilon\in[0,1/2)$ (called an _error bound_) such that, for
every input $x$, either $p_{M,acc}(x)\geq 1-\varepsilon$ or $p_{M,rej}(x)\geq
1-\varepsilon$; otherwise, we say that $M$ makes _unbounded error_.

Regarding the behavioral equivalence of probabilistic machines, two 1ppda’s
$M_{1}$ and $M_{2}$ are said to be _error-equivalent_ to each other if
$L(M_{1})=L(M_{2})$ and $M_{1}$ simulates $M_{2}$ (or $M_{2}$ simulates
$M_{1}$) with exactly the same error probability on every input. In this
paper, we are also concerned with the descriptional complexity of machine
models. We use the following three complexity measures to describe each
machine $M$. The _state size_ (or _state complexity_) of $M$ is $|Q|$, the
_stack alphabet size_ of $M$ is $|\Gamma|$, and the _push size_ of $M$ is the
maximum length of any string in $\Theta_{\Gamma}$. It then follows that
$|\Theta_{\Gamma}|\leq m^{e}$ if $M$ has stack alphabet size $m$ and push size
$e$.

###  2.3 The Second Formulation

In comparison with the first formulation, let us consider 1ppda’s with no
endmarker. Such machines are succinctly called _no-endmarker 1ppda’s_ and they
are naturally obtained from all the definitions stated in Section 2.2 except
for removing the entire use of ${|}\\!\\!\mathrm{c}$ and $\$$. For example, an
_input region_ is now the cells that contain $x$, instead of
${|}\\!\\!\mathrm{c}x\$$. We express such a machine as
$(Q,\Sigma,\Theta_{\Gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$ without
${|}\\!\\!\mathrm{c}$ and $\$$. For such a no-endmarker 1ppda, its
probabilistic transition function $\delta$ maps
$Q\times\Sigma_{\lambda}\times\Gamma\times Q\times\Theta_{\Gamma}$ to $[0,1]$,
where $\Sigma_{\lambda}=\Sigma\cup\\{\lambda\\}$. The acceptance and rejection
of such no-endmarker 1ppda’s are determined by whether the 1ppda’s are
respectively in accepting states or in rejecting states just after reading off
the entire input string and leaving the input region. To ensure this, $Q$ must
be partitioned into $Q_{acc}$ and $Q_{rej}$.

It is important to note that every 1ppda in the initial state must read the
leftmost symbol of a given non-empty input string written on the input tape at
the first step. In particular, when an input is the empty string, for any
machine that has the right endmarker but no left endmarker, it can still read
$\$$ at the first step. In contrast, since a no-endmarker machine cannot
“read” any blank symbol, we must allow the machine to make a $\lambda$-move at
the first step.

###  2.4 Deterministic and Nondeterministic Variants

Deterministic and nondeterministic variants of 1ppda’s can be easily obtained
by slightly modifying the definition of the 1ppda’s. To obtain a _one-way
deterministic pushdown automaton_ (or a 1dpda), we require
$\delta(q,\sigma,a\\!\mid\\!p,u)\in\\{0,1\\}$ (instead of the unit real
interval $[0,1]$) for all tuples $(q,\sigma,a,p,u)$. Similarly, we can obtain
_one-way nondeterministic pushdown automata_ (or 1npda’s) if we pick a
possible next move uniformly at random and take the following
acceptance/rejection criteria: a 1npda $M$ accepts input $x$ if
$p_{M,acc}(x)>0$ and $M$ rejects $x$ if $p_{M,rej}(x)=1$. It is not difficult
to see that these “probabilistic” definitions of 1dpda’s and 1npda’s coincide
with the “standard” definitions written in many textbooks.

##  3 From No-Endmarker 1ppda’s to Endmarker 1ppda’s

Proposition 1.3 asserts a linear increase of the stack-state complexity of
transforming no-endmarker 1ppda’s into error-equivalent endmarker 1ppda’s.
Although the transformation seems rather easy, we briefly describe how to
construct from any no-endmarker 1ppda $M$ an error-equivalent endmarker 1ppda
$N$.

Proof of Proposition 1.3.  Given any no-endmarker 1ppda
$M=(Q,\Sigma,\Gamma,\Theta_{\Gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$, we
construct an endmarker 1ppda
$N=(Q^{\prime},\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma^{\prime},\Theta_{\Gamma^{\prime}},\delta^{\prime},q^{\prime}_{0},Z_{0},Q^{\prime}_{acc},Q^{\prime}_{rej})$,
where $Q^{\prime}_{acc}=\\{\hat{q}\mid q\in Q_{acc}\\}$,
$Q^{\prime}_{rej}=\\{\hat{q}\mid q\in Q_{rej}\\}$,
$Q^{\prime}=Q\cup\\{q^{\prime}_{0}\\}\cup Q^{\prime}_{acc}\cup
Q^{\prime}_{rej}$, and
$\Gamma^{\prime}=\Gamma\cup\\{{|}\\!\\!\mathrm{c},\$\\}$. It follows that
$|Q^{\prime}|\leq 2n+1$ and $|\Gamma^{\prime}|=m+2$ and that the push size
does not change.

Intuitively speaking, the behavior of $N$ is described as follows. In the
first move, $N$ uses a new initial state $q^{\prime}_{0}$ to read the left
endmarker ${|}\\!\\!\mathrm{c}$ and then enters $M$’s initial state $q_{0}$
(in Line 1 below). Note that, while reading a non-$\lambda$ symbol, by the
definition, $M$ does not halt even if it enters halting states. When $M$ is in
a halting state after reading the rightmost input symbol and making a series
of (possible) $\lambda$-moves, $N$ then reads $\$$ and enters new but
corresponding halting states without changing the stack content (in Line 3).
Formally, we define the probabilistic transition function $\delta^{\prime}$ as
follows. Let $\Sigma_{\lambda}=\Sigma\cup\\{\lambda\\}$.

  1. 1.

$\delta^{\prime}(q^{\prime}_{0},{|}\\!\\!\mathrm{c},Z_{0}\\!\mid\\!q_{0},Z_{0})=1$

  2. 2.

$\delta^{\prime}(q,\sigma,a\\!\mid\\!p,w)=\delta(q,\sigma,a\\!\mid\\!p,w)$ for
$q\in Q$, $a\in\Gamma$, and $\sigma\in\Sigma_{\lambda}$.

  3. 3.

$\delta^{\prime}(q,\$,a\\!\mid\\!\hat{q},a)=1$ for $q\in Q_{halt}$ and
$a\in\Gamma$ if $\delta[q,\lambda,a]=0$.

It is not difficult to show that $N$ simulates $M$ correctly with the same
error probability. This completes the proof of Proposition 1.3. $\Box$

##  4 Preparatory Machine Modifications

A key to our proof of Proposition 1.4 is the step to normalize the wild
behaviors of endmarker 1ppda’s without compromising their error probability.
This preparatory step is quite crucial and it will help us prove the
proposition significantly more easily in Section 5. In the nondeterministic
model, it is always possible to eliminate all $\lambda$-moves of 1npda’s and
limit the set $Q$ of inner states to $Q_{simple}=\\{q_{0},q,q_{acc}\\}$ (this
is a byproduct of translating a context-free grammar in Greibach Normal Form
to a corresponding 1npda). For 1ppda’s, however, we can neither eliminate
$\lambda$-moves nor limit $Q$ to $Q_{simple}$. Moreover, we cannot control the
number of consecutive $\lambda$-moves. Despite all those difficulties, we can
still curtail certain behaviors of 1ppda’s to control the execution of push
and pop operations during their computations. Such a push-pop-controlled form
is called “ideal shape.”

For to 1npda’s and 1dpda’s, there are a few precursors in this direction:
Hopcroft and Ullman [3, Chapter 10] and Pighizzini and Pisoni [11, Section 5].
We intend to utilize the basic ideas of them and further expand the ideas to
prove that all 1ppda’s can be transformed into their ideal-shape form.

###  4.1 No Halting Before Reading $

We first modify a given endmarker 1ppda to another one with a certain nice
property without compromising its error probability. In particular, we want to
eliminate the possibility of premature halting well before reading $\$$;
namely, to force the machine to halt only on or after reading $\$$ with a
(possible) series of subsequent $\lambda$-moves. Recall that a stack is
_empty_ when it contains only the bottom marker.

###### Lemma 4.1

Given any endmarker 1ppda $M$ with $n$ states, $m$ stack alphabet size, and
$e$ push size, there exists an error-equivalent endmarker 1ppda $N$ having
$2n+2$ states with stack alphabet size $m$ and push size $e$ such that it
halts only on or after reading $\$$; moreover, when $N$ halts, its stack
becomes empty.

A proof idea of Lemma 4.1 is to simulate $M$ step by step until $M$ either
enters a halting state or reads $\$$. When $M$ enters a halting state before
reading $\$$, $N$ remembers this state, empties the stack, continues reading
input symbols, and finally enters a true halting state. On the contrary, when
$M$ reaches $\$$, $N$ remembers the passing of $\$$, continues the simulation
of $M$’s $\lambda$-moves. Once $M$ enters a halting state, $N$ remembers this
state, empties the stack, and enters a true halting state.

For the clarity of the state complexity term of $2n+2$ in Lemma 4.1 and also
for the later use of the lemma’s proof in Section 4.2, we include the detailed
proof of the lemma.

Proof of Lemma 4.1.  Let
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},Q_{acc},Q_{rej})$
be any 1ppda with $|Q|=n$, $|\Gamma|=m$, and push size $e$. In the following,
we define the desired 1ppda
$N=(Q^{\prime},\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma^{\prime},\Theta_{\Gamma^{\prime}},\delta^{\prime},q^{\prime}_{0},Q^{\prime}_{acc},Q^{\prime}_{rej})$
that can simulate $M$ with the same error probability. Firstly, we prepare a
new non-halting inner state $\bar{q}$, which corresponds to each state $q$ in
$Q_{halt}$, and new accepting and rejecting states $q^{\prime}_{acc}$ and
$q^{\prime}_{rej}$. We set $Q^{(0)}=\\{\bar{q}\mid q\in Q_{rej}\\}$ and
$Q^{(1)}=\\{\bar{q}\mid q\in Q_{acc}\\}$. We also prepare $\bar{q}^{(\$)}$ for
each state $q$ in $Q-Q_{halt}$ and define $Q^{(\$)}=\\{\bar{q}^{(\$)}\mid q\in
Q\\}$. Moreover, we define $Q^{\prime}_{acc}=\\{q^{\prime}_{acc}\\}$,
$Q^{\prime}_{rej}=\\{q^{\prime}_{rej}\\}$, $Q^{\prime}=(Q-Q_{halt})\cup
Q^{(\$)}\cup Q^{(0)}\cup Q^{(1)}\cup Q^{\prime}_{acc}\cup Q^{\prime}_{rej}$,
and $\Gamma^{\prime}=\Gamma$. Recall from Section 2.2 the notation
$\check{\Sigma}=\Sigma\cup\\{{|}\\!\\!\mathrm{c},\$\\}$ and
$\check{\Sigma}_{\lambda}=\check{\Sigma}\cup\\{\lambda\\}$. In what follows,
we describe how to define $\delta^{\prime}$, which aims at simulating $M$ step
by step on a given input. Let us consider two cases, depending on whether or
not $M$ reads $\$$.

(1) When $M$ enters an accepting state (resp., a rejecting state), say, $q$
before reading $\$$, $N$ first enters its associated state $\bar{q}$, empties
the stack, and continues reading the rest of an input string
deterministically. When $N$ finally reaches $\$$ in state $\bar{q}$ in
$Q_{acc}$ (resp., $Q_{rej}$), $N$ changes it to $q^{\prime}_{acc}$ (resp.,
$q^{\prime}_{rej}$) and halt. Formally, $\delta^{\prime}$ is set as follows.
Let $q\in Q$, $p\in Q^{\prime}$, $a\in\Gamma$,
$\sigma,\tau\in\check{\Sigma}_{\lambda}$, and $w\in\Theta_{\Gamma}$.

  1. 1.

$\delta^{\prime}(p,\sigma,a\\!\mid\\!q,w)=\delta(p,\sigma,a\\!\mid\\!q,w)$ if
$q\notin Q_{halt}$ and $\sigma\in\check{\Sigma}_{\lambda}$.

  2. 2.

$\delta^{\prime}(p,\sigma,a\\!\mid\\!\bar{q},w)=\delta(p,\sigma,a\\!\mid\\!q,w)$
if $\sigma\in\Sigma_{\lambda}\cup\\{{|}\\!\\!\mathrm{c}\\}$ and $q\in
Q_{halt}$.

  3. 3.

$\delta^{\prime}(\bar{q},\lambda,a\\!\mid\\!\bar{q},\lambda)=1$ if
$a\in\Gamma^{(-)}$ and $q\in Q_{halt}$.

  4. 4.

$\delta^{\prime}(\bar{q},\tau,Z_{0}\\!\mid\\!\bar{q},Z_{0})=1$ if
$\tau\in\Sigma$ and $q\in Q_{halt}$.

  5. 5.

$\delta^{\prime}(\bar{q},\$,Z_{0}\\!\mid\\!\hat{q},Z_{0})=1$, where
$\hat{q}=q^{\prime}_{acc}$ if $q\in Q_{acc}$, and $\hat{q}=q^{\prime}_{rej}$
if $q\in Q_{rej}$.

(2) On the contrary, when $M$ reaches $\$$ in a non-halting state, say, $q$,
the new machine $N$ enters $\bar{q}^{(\$)}$ and then simulates $M$’s
$\lambda$-moves using corresponding states in $Q^{(\$)}$. After making a
series of consecutive $\lambda$-moves, when $M$ enters an accepting state
(resp., a rejecting state), say, $q$, $N$ enters its corresponding state
$\bar{q}^{(\$)}$, deterministically empties the stack, and finally enters
$q^{\prime}_{acc}$ (resp., $q^{\prime}_{rej}$). Formally, $\delta^{\prime}$ is
defined as follows. Let $p\in Q^{\prime}$, $q\in Q$, $a\in\Gamma$, and
$w\in\Theta_{\Gamma}$.

  1. 6.

$\delta^{\prime}(p,\$,a\\!\mid\\!\bar{q}^{(\$)},w)=\delta(p,\$,a\\!\mid\\!q,w)$
if $q\notin Q_{halt}$.

  2. 7.

$\delta^{\prime}(\bar{p}^{(\$)},\lambda,a\\!\mid\\!\bar{q}^{(\$)},w)=\delta(p,\lambda,a\\!\mid\\!q,w)$.

  3. 8.

$\delta^{\prime}(\bar{p}^{(\$)},\lambda,a\\!\mid\\!\bar{p}^{(\$)},\lambda)=1$
if $a\in\Gamma^{(-)}$.

  4. 9.

$\delta^{\prime}(\bar{p}^{(\$)},\lambda,Z_{0}\\!\mid\\!\hat{q},Z_{0})=1$ if
$p\in Q_{halt}$, where $\hat{q}=q^{\prime}_{acc}$ if $q\in Q_{acc}$, and
$\hat{q}=q^{\prime}_{rej}$ otherwise.

It is not difficult to show that $N$ simulates $M$ on every input and $N$ errs
with the same probability as $M$ does. Note that $|Q^{\prime}|=2n+2$ and that
both the stack alphabet size and the push size are unaltered. $\Box$

###  4.2 Transforming 1ppda’s to the Ideal-Shape Form

We next convert a 1ppda into a specific form, called an “ideal shape,” where
the 1ppda takes a “push-pop-controlled form,” in which pop operations always
take place by reading a non-blank input symbol $\sigma$ and then making a
(possible) series of pop operations without reading any other input symbol and
push operations add only single symbols without altering any existing stack
content.

Any 1ppda with $Q$, $\Sigma$, $\Gamma$, and $\delta$ is said to be _in an
ideal shape_ if the following conditions (1)–(5) are all satisfied. (1)
Scanning $\sigma\in\Sigma$, it preserves the topmost stack symbol (called a
_stationary operation_). (2) Scanning $\sigma\in\Sigma$, it pushes a new
symbol $b$ ($\in\Gamma^{(-)}$) without changing any symbol stored in the
stack. (3) Scanning $\sigma\in\Sigma$, it pops the topmost stack symbol. (4)
Without scanning any input symbol (i.e., making a $\lambda$-move), it pops the
topmost stack symbol. (5) The stack operation (4) comes only after either (3)
or (4). For later convenience, we refer to these five conditions as the
_ideal-shape conditions_.

More formally, the ideal-shape conditions are described using $\delta$ in the
following way. Let $p,q\in Q$, $\sigma\in\check{\Sigma}$, $u\in\Gamma^{*}$,
and $a\in\Gamma$.

  1. 1.

If $\delta(q,\sigma,a\\!\mid\\!p,u)\neq 0$, then $u$ is in
$\\{\lambda,ba,a\\}$ for a certain $b\in\Gamma^{(-)}$.

  2. 2.

If $\delta(q,\lambda,a\\!\mid\\!p,u)\neq 0$ and $a\neq Z_{0}$, then
$u=\lambda$.

  3. 3.

If $\delta(q,\sigma,a\\!\mid\\!p,ba)\neq 0$ for a certain $b\in\Gamma^{(-)}$,
then $\delta[p,\lambda,b]=0$

  4. 4.

If $\delta(q,\sigma,a\\!\mid\\!p,a)\neq 0$, then $\delta[p,\lambda,a]=0$.

Notice that Conditions 1–2 are related to the stack operations of (1)–(4)
described above and that Conditions 3–4 are related to the condition (5). For
no-endmarker 1ppda’s, nonetheless, we can define the same notion of “ideal
shape” by requiring Conditions 1–4 to hold _only for nonempty inputs_.

Lemma 4.2 states that any 1ppda can be converted into its error-equivalent
1ppda in an ideal shape.

###### Lemma 4.2

[Ideal Shape Lemma] Let $n\in\mathbb{N}^{+}$. Any $n$-state endmarker 1ppda
$M$ with stack alphabet size $m$ and push size $e$ can be converted into
another error-equivalent 1ppda $N$ in an ideal shape with
$O(en^{2}m^{2}(2m)^{2enm})$ states and stack alphabet size
$O(enm(2m)^{2enm})$. The above statement is also true for no-endmarker
1ppda’s.

The proof of the lemma partly follows the arguments of Hopcroft and Ullman [3,
Chapter 10] and of Pighizzini and Pisoni [11, Section 5]. In the proof, the
desired conversion of a given 1ppda $M$ into its error-equivalent ideal-shape
1ppda $N$ is carried out stage by stage. Firstly, $M$ is converted into
another 1ppda $M_{1}$ whose $\lambda$-moves are limited only to pop
operations. This $M_{1}$ is further modified into another 1ppda $M_{2}$, which
satisfies (2)–(3) of the ideal-shape conditions together with the extra
condition that all $\lambda$-moves are limited to either pop operations or
exchanges of a topmost stack symbol with one symbol. From this $M_{2}$, we
construct another 1ppda $M_{3}$, which satisfies (1)–(3) of the ideal-shape
conditions. Finally, we modify $M_{3}$ into another 1ppda $M_{4}$, which
further forces the ideal shape condition (5) to meet. This last machine
$M_{4}$ becomes the desired 1ppda $N$.

Proof of Lemma 4.2.  Let
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$
be any endmarker 1ppda with $|Q|=n$, $|\Gamma|=m$, and push size $e$. We first
apply Lemma 4.1 to obtain another 1ppda that halts only on or after reading
$\$$. We recall the notation used in the proof of Lemma 4.1. Notice that the
obtained machine in the proof uses only a distinguished set $Q^{(\$)}$ of
inner states after reading $\$$ and that, when it halts, its stack becomes
empty. Moreover, we recall the two halting states $q^{\prime}_{acc}$ and
$q^{\prime}_{rej}$ from the proof. Here, we set
$Q_{acc}=\\{q^{\prime}_{acc}\\}$ and $Q_{rej}=\\{q^{\prime}_{rej}\\}$. For
readability, we also call the obtained 1ppda by $M$ and assume that $|Q|=2n+2$
and $|\Gamma|=m$. Let $\Gamma_{\lambda}=\Gamma\cup\\{\lambda\\}$. Starting
with this new machine $M$, we perform a series of conversions to satisfy the
desired ideal-shape conditions. In the process of such conversions, we denote
by
$M_{i}=(Q_{i},\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma_{i},\Theta_{\Gamma_{i}},\delta_{i},q_{i,0},Z_{i,0},Q_{i,acc},Q_{i,rej})$
the 1ppda with push size $e_{i}$ obtained at stage $i\in[4]$.

To our description simpler, we further introduce the succinct notation
$\delta^{*}[q,\lambda,a\\!\mid\\!p,\lambda,w]$ (where $q\in Q-Q_{halt}$, $p\in
Q$, $a\in\Gamma$, and $w\in\Gamma^{*}$) for the total probability of the event
that, starting in state $q$ with stack content $az$ (for an “arbitrary” string
$z\in\Gamma^{+}$), $M$ makes a (possible) series of consecutive
$\lambda$-moves without accessing any symbol in $z$, and eventually reaches
inner state $p$ with stack content $wz$. This notation is formally defined as
$\delta^{*}[q,\lambda,a\\!\mid\\!p,\lambda,w]=\sum_{t\geq
0}\delta^{(t)}[q,\lambda,a\\!\mid\\!p,\lambda,w]$, where $\delta^{(t)}$ is
introduced in the following inductive way. Let $q\in Q-Q_{halt}$,
$a\in\Gamma$, and $w\in\Gamma^{*}$.

  1. (a)

$\delta^{(0)}[q,\lambda,a\\!\mid\\!q,\lambda,a]=1$ and
$\delta^{(0)}[q,\lambda,a\\!\mid\\!p,\lambda,w]=0$ for any $(p,w)\neq(q,a)$.

  2. (b)

$\delta^{(t+1)}[q,\lambda,a\\!\mid\\!p,\lambda,\lambda]=0$ and
$\delta^{(t+1)}[q,\lambda,a\\!\mid\\!p,\lambda,w]=\sum_{r,b,u,u^{\prime}}\delta^{(t)}[q,\lambda,a\\!\mid\\!r,\lambda,bu]\delta(r,\lambda,b\\!\mid\\!p,u^{\prime})$
if $w\neq\lambda$, where $b\in\Gamma$, $r\in Q$, and
$w=u^{\prime}u\in\Gamma^{+}$.

Notice that, in particular,
$\delta^{*}[q,\lambda,a\\!\mid\\!p,\lambda,\lambda]=0$ follows.

By our definition of 1ppda’s, all computation paths must terminate eventually
on every input $x$. Thus, any series of consecutive $\lambda$-moves makes the
stack height increase by no more than $e|Q||\Gamma|$ because, otherwise, the
series produces an infinite computation path. It thus follows that (*)
$\delta^{*}[q,\lambda,a\\!\mid\\!p,\lambda,w]\neq 0$ implies $|w|\leq
e|Q||\Gamma|=e(n+2)m\leq 2enm$.

(1) We first convert the original 1ppda $M$ to another error-equivalent 1ppda,
say, $M_{1}$ whose $\lambda$-moves are restricted only to pop operations;
namely, $\delta_{1}(q,\lambda,a\\!\mid\\!p,w)=0$ for all elements $p,q\in Q$,
$a\in\Gamma$, and $w\in\Gamma^{+}$. For this purpose, we need to remove any
$\lambda$-move by which $M$ changes topmost stack symbol $a$ to a certain
nonempty string $w$. We also need to remove all transitions of the form
$\delta(q,\lambda,Z_{0}\\!\mid\\!p,Z_{0})$, which violates the requirement of
$M_{1}$ concerning pop operations. Notice that, once $M$ reads $\$$, it makes
only $\lambda$-moves with inner states in $Q^{(\$)}$ and eventually empties
the stack.

We define $Q_{1}=Q\cup Q^{(\$)}$, $Q_{1,acc}=Q_{acc}\cup\\{q^{(\$)}\mid q\in
Q_{acc}\\}$, $Q_{1,rej}=Q_{rej}\cup\\{q^{(\$)}\mid q\in Q_{rej}\\}$, and
$\Gamma_{1}=\Gamma^{(-)}\cup\\{Z_{0},Z_{1,0}\\}$, where $Z_{1,0}$ is a new
bottom marker not in $\Gamma$. Moreover, we set $q_{1,0}$ to be $q_{0}$. It
then follows from the above definition of $M_{1}$ that $|Q_{1}|=2|Q|=4(n+1)$
and $|\Gamma_{1}|=m+1$. By Statement (*), the push size $e_{1}$ of $M_{1}$ is
at most $2enm$. The probabilistic transition function $\delta_{1}$ is
constructed formally in the following substages (i)–(iii). For any value of
$\delta_{1}$ not listed below is assumed to be $0$.

(i) Recall that the first step of any 1ppda must be a non-$\lambda$-move in
general. At the first step, $M_{1}$ changes $Z_{1,0}$ to $uZ_{0}Z_{1,0}$ (for
an appropriate string $u\in(\Gamma^{(-)})^{*}$) so that, after this step,
$M_{1}$ simulates $M$ using $Z_{0}$ as a standard stack symbol but with no
access to $Z_{1,0}$ (except for the final step of $M_{1}$). This process is
expressed as follows.

  1. 1.

$\delta_{1}(q_{0},{|}\\!\\!\mathrm{c},Z_{1,0}\\!\mid\\!p,uZ_{0}Z_{1,0})=\delta(q_{0},{|}\\!\\!\mathrm{c},Z_{0}\\!\mid\\!p,uZ_{0})$
for $u$ satisfying $uZ_{0}\in\Theta_{\Gamma}$.

(ii) Assume that $az$ is $M$’s stack content and $M$ makes a (possible) series
of consecutive $\lambda$-moves by which $M$ never accesses any stack symbol in
$z$. Consider the case where $M$ changes $a$ to $bu$ by the end of the series
and, at reading symbol $\sigma\in\Sigma\cup\\{\$\\}$, $M$ replaces $b$ with
$u^{\prime}$ at the next step in order to produce $w$ ($=u^{\prime}u$). In
this case, we merge this entire process into one single non-$\lambda$-move.

  1. 2.

$\delta_{1}(q,\sigma,a\\!\mid\\!p,w)=\sum_{r,b,u,u^{\prime}}\delta^{*}[q,\lambda,a\\!\mid\\!r,\lambda,bu]\delta(r,\sigma,b\\!\mid\\!p,u^{\prime})$
if $\sigma\in\Sigma$, $q\notin Q^{(\$)}$, and $a\in\Gamma$, where
$w=u^{\prime}u\in\Gamma^{*}$ and $b\in\Gamma$.

  2. 3.

$\delta_{1}(q,\$,a\\!\mid\\!p^{(\$)},w)=\sum_{r,b,u,u^{\prime}}\delta^{*}[q,\lambda,a\\!\mid\\!r,\lambda,bu]\delta(r,\$,b\\!\mid\\!p,u^{\prime})$
if $a\in\Gamma$, where $w=u^{\prime}u\in\Gamma^{*}$ and $b\in\Gamma$.

Since we obtain
$\delta_{1}(q,\sigma,a\\!\mid\\!p,\lambda)=\sum_{r,b}\delta^{*}[q,\lambda,a\\!\mid\\!r,\lambda,b]\delta(r,\$,b\\!\mid\\!p,\lambda)$,
non$-\lambda$-moves of $M_{1}$ may contain pop operations. Lines 1–3 indicate
that the new push size $e_{1}$ is exactly $e+1$, and thus
$\Theta_{\Gamma_{1}}\subseteq\Gamma_{1}^{\leq e_{1}}$ follows.

Let us consider the case where, with a certain probability, $M$ produces a
stack content $bz$ by the end of the series of $\lambda$-moves and then pops
$b$ at the next step without reading any input symbol. In this case, we also
merge this entire process into a single $\lambda$-move of pop operation as
described below.

  1. 4.

$\delta_{1}(q,\lambda,a\\!\mid\\!p,\lambda)=\sum_{r,b}\delta^{*}[q,\lambda,a\\!\mid\\!r,\lambda,b]\delta(r,\lambda,b\\!\mid\\!p,\lambda)$
for $q\in Q-Q_{halt}$ and $a\in\Gamma^{(-)}$, where $r\in Q$ and $b\in\Gamma$.

(iii) Assume that $M$ has already read $\$$ but $M$ is still in a non-halting
state, say, $q^{(\$)}$ in $Q^{(\$)}$ making a series of consecutive
$\lambda$-moves. Unless $M$ reaches $Z_{0}$, similarly to Line 4., we merge
this series of $\lambda$-moves and one pop operation into a single
$\lambda$-move.

  1. 5.

$\delta_{1}(q^{(\$)},\lambda,a\\!\mid\\!p^{(\$)},\lambda)=\sum_{r,b}\delta^{*}[q^{(\$)},\lambda,a\\!\mid\\!r^{(\$)},\lambda,b]\delta(r^{(\$)},\lambda,b\\!\mid\\!p^{(\$)},\lambda)$
for $a\in\Gamma^{(-)}$, $r^{(\$)}\notin Q_{halt}$, and $b\in\Gamma$, where
$r\in Q$ and $b\in\Gamma$.

Once $M$ enters an inner state $p^{(\$)}$ in $Q_{halt}$ at scanning $Z_{0}$,
we remove $Z_{0}$ and enter the same halting state.

  1. 6.

$\delta_{1}(q^{(\$)},\lambda,Z_{0}\\!\mid\\!p^{(\$)},\lambda)=\delta^{*}[q^{(\$)},\lambda,Z_{0}\\!\mid\\!p^{(\$)},\lambda,Z_{0}]$
for $q^{(\$)}\notin Q_{halt}$ and $p^{(\$)}\in Q_{halt}$.

(2) We next convert $M_{1}$ to another error-equivalent 1ppda $M_{2}$ that
conducts only the following types of moves: ($a$) $M$ pushes one symbol
without changing the exiting stack content, ($b$) it replaces the topmost
stack symbol by a (possibly different) single symbol, and ($c$) it pops the
topmost stack symbol. We also demand that all $\lambda$-moves of $M_{2}$ are
limited only to either ($b$) or ($c$). From these conditions, we obtain
$e_{2}=2$.

To describe the intended conversion, we introduce two notations. The first
notation $[w]$ represents a new stack symbol that encodes an element $w$ in
$\Gamma_{1}^{\leq e_{1}}$. To make $M_{2}$ remember the topmost stack symbol
of $M_{1}$, we introduce another notation $[q,a]$ indicating that $M_{1}$ is
in inner state $q$ reading $a$ in the stack.

We set $Q_{2}=[Q_{1},\Gamma_{1}]$, $\Gamma_{2}=\\{[w]\mid w\in\Gamma_{1}^{\leq
e_{1}},\exists b\in\Gamma_{1}\,\exists
u\in\Gamma_{1}^{*}\,[buw\in\Theta_{\Gamma_{1}}]\\}\cup\\{[a]\mid
a\in\Gamma_{1}\\}$. Let $Z_{2,0}=[Z_{1,0}]$ denote a new bottom marker and let
$q_{2,0}=[q_{1,0},Z_{1,0}]$ denote a new initial state. It then follows that
$|Q_{2}|=|Q_{1}||\Gamma_{1}|\leq 6nm$ and $|\Gamma_{2}|\leq
e_{1}|\Theta_{\Gamma_{1}}|+|\Gamma_{1}|\leq
e_{1}|\Gamma_{1}|^{e_{1}+1}+|\Gamma_{1}|\leq e(n+2)m(2m)^{e(n+2)m+1}+2m\leq
2enm(2m)^{2enm}$ since $|\Theta_{\Gamma_{1}}|\leq|\Gamma_{1}|^{\leq
e_{1}}=|\Gamma_{1}|^{e_{1}+1}$.

(i) Consider the case where $M_{1}$ reads
$(\sigma,a)\in\check{\Sigma}\times\Gamma$, substitutes $bu$ (with $b\in\Gamma$
and $u\in\Gamma^{*}$) for $a$, and enters inner state $p$. In this case,
$M_{2}$ reads $(\sigma,[w])$ with a current topmost stack symbol of the form
$[w]\in\Gamma_{2}$, changes it to $[u][w]$ (or $[w]$ if $u=\lambda$), and
enters state $[p,b]$. Let $p,q\in Q_{1}$, $\sigma\in\check{\Sigma}$,
$b\in\Gamma_{1}$, and $u,w\in\Gamma_{1}^{\leq e_{1}}$. This process is
described as follows.

  1. 1.

$\delta_{2}([q,a],\sigma,[w]\\!\mid\\![p,b],[u][w])=\delta_{1}(q,\sigma,a\\!\mid\\!p,bu)$
if $u\neq\lambda$.

  2. 2.

$\delta_{2}([q,a],\sigma,[w]\\!\mid\\![p,b],[w])=\delta_{1}(q,\sigma,a\\!\mid\\!p,b)$.

(ii) Assuming that $M_{1}$ reads $(\lambda,a)$ and pops $a$ by entering state
$p$, if $w\neq\lambda$, then $M_{2}$ reads $(\sigma,[bw])$ in state $[q,a]$
and changes $[bw]$ to $[w]$ by entering inner state $[p,b]$. The function
$\delta_{2}$ is formally defined as follows.

  1. 3.

$\delta_{2}([q,a],\lambda,[bw]\\!\mid\\![p,b],[w])=\delta_{1}(q,\sigma,a\\!\mid\\!p,\lambda)$
if $w\neq\lambda$.

  2. 4.

$\delta_{2}([q,a],\lambda,[b]\\!\mid\\![p,b],\lambda)=\delta_{1}(q,\sigma,a\\!\mid\\!p,\lambda)$
if $b\neq Z_{1,0}$.

(iii) Finally, we need to deal with the special case of $[q_{0},Z_{1,0}]$.
Because $Z_{1,0}$ is the bottom marker of $M_{1}$, a slightly different
treatment is required as shown below. Notice that
$\delta_{1}(q,\sigma,Z_{1,0}\\!\mid\\!p,wZ_{1,0})=0$ if
$(1,\sigma)\neq(q_{0},{|}\\!\\!\mathrm{c})$.

  1. 5.

$\delta_{2}([q_{0},Z_{1,0}],{|}\\!\\!\mathrm{c},[Z_{1,0}]\\!\mid\\![u,Z_{0}][Z_{1,0}])=\delta_{1}(q_{0},{|}\\!\\!\mathrm{c},Z_{1,0}\\!\mid\\!p,buZ_{0}Z_{1,0})$.

Clearly, $e_{2}=2$ holds.

(3) We further convert $M_{2}$ to $M_{3}$ so that $M_{3}$ satisfies (2) and,
moreover, there is no stationary operation that replaces any topmost symbol
with a “different” single symbol. This is done by remembering the topmost
stack symbol without writing it down into the stack. For this purpose, we use
a new symbol of the form $[q,a]$ (where $q\in Q_{2}$ and $a\in\Gamma_{2}$) to
indicate that $M_{2}$ is in state $q$, reading $a$ in the stack. Let
$Q_{3}=[Q_{2},\Gamma_{2}]$, $q_{3,0}=[q_{2,0},Z_{2,0}]$, and
$\Gamma_{3}=\Gamma_{2}\cup\\{Z_{3,0}\\}$, where $Z_{3,0}$ is the new bottom
marker of $M_{3}$. We then obtain $|Q_{3}|=|Q_{2}||\Gamma_{2}|\leq
2en^{2}m^{2}(2m)^{enm}$ and $\Gamma_{3}|\leq 2enm(2m)^{2enm}$.

Furthermore, similarly to $\delta^{*}[q,\lambda,a\\!\mid\\!p,\lambda,w]$, we
define $\delta_{2}^{*}[q,\lambda,a\\!\mid\\!p,\lambda,w]$ from $\delta_{2}$ to
merge a series of consecutive $\lambda$-moves. If $M_{2}$ makes a series of
$\lambda$-moves of changing $(q,a)$ to $(r,d)$ followed by a
non-$\lambda$-move of changing $(r,d)$ to $(p,b)$ (resp., $(p,bd)$) while
reading symbol $\sigma$, then $M_{3}$ reads $(\sigma,c)$ for a certain topmost
symbol $c$, and changes its inner state $[q,a]$ to $[p,b]$ without changing
$c$ (resp., with changing $c$ to $ac$). In contrast, if $M_{2}$ changes to
$(p,b)$, after a series of $\lambda$-moves, from $(q,a)$, then $\delta_{3}$
satisfies Condition 4. Note that a pop operation of $M_{3}$ is performed only
at a certain $\lambda$-move.

Formally, $\delta_{3}$ is constructed as follows. Let $p,q\in Q_{2}$ and
$a,b\in\Gamma_{2}$, $c\in\Gamma_{3}$, and $\sigma\in\check{\Sigma}$.

  1. 1.

$\delta_{3}([q,a],\sigma,c\\!\mid\\![p,b],c)=\sum_{r,d}\delta_{2}^{*}[q,\lambda,a\\!\mid\\!r,\lambda,d]\delta_{2}(r,\sigma,d\\!\mid\\!p,b)$.

  2. 2.

$\delta_{3}([q,a],\sigma,c\\!\mid\\![p,b],ac)=\sum_{r,d}\delta_{2}^{*}[q,\lambda,a\\!\mid\\!r,\lambda,d]\delta_{2}(r,\sigma,d\\!\mid\\!p,bd)$.

  3. 3.

$\delta_{3}([q,a],\lambda,c\\!\mid\\![p,c],\lambda)=\sum_{r,d}\delta_{2}^{*}[q,\lambda,a\\!\mid\\!r,\lambda,d]\delta_{2}(r,\lambda,d\\!\mid\\!p,\lambda)$.

  4. 4.

$\delta_{3}([q,a],\lambda,c\\!\mid\\![p,b],c)=\sum_{r,d}\delta_{2}^{*}[q,\lambda,a\\!\mid\\!r,\lambda,d]\delta_{2}(r,\lambda,d\\!\mid\\!p,b)$.

(4) We convert $M_{3}$ to $M_{4}$ that satisfies (3) and also makes only
$\lambda$-moves of pop operations that follow only a (possible) series of pop
operations. Let $Q_{4}=Q_{3}\cup\\{p^{\prime}\mid p\in Q_{halt}\\}$ and
$\Gamma_{4}=\Gamma_{3}$. Let $q_{4,0}=q_{3,0}$ and $Z_{4,0}=Z_{3,0}$. It
follows that $|Q_{4}|\leq 2|Q_{3}|\leq 48en^{2}m^{2}(2m)^{2enm}$ and
$|\Gamma_{4}|\leq 4enm(2m)^{2enm}$. The probabilistic transition function
$\delta_{4}$ is constructed as follows. A basic idea of our construction is
that, when $M_{3}$ makes a pop operation after a certain non-pop operation, we
combine them as a single move. As a new notation, we define $\hat{p}=p$ if
$p\notin Q_{3,halt}$ and $\hat{p}=p^{\prime}$ otherwise. Let
$\sigma\in\check{\Sigma}_{\lambda}$.

  1. 1.

$\delta_{4}(q,\sigma,a\\!\mid\\!\hat{p},\lambda)=\sum_{r}\delta_{3}(q,\sigma,a\\!\mid\\!r,a)\delta_{3}(r,\lambda,a\\!\mid\\!p,\lambda)$.

  2. 2.

$\delta_{4}(q,\sigma,a\\!\mid\\!\hat{p},a)=\sum_{r}\delta_{3}(q,\sigma,a\\!\mid\\!r,ba)\delta_{3}(r,\lambda,b\\!\mid\\!p,\lambda)$
if $\sigma\neq\lambda$.

  3. 3.

$\delta_{4}(q,\sigma,a\\!\mid\\!p,ba)=\delta_{3}(q,\sigma,a\\!\mid\\!p,ba)$ if
$\sum_{s\in Q_{3}}\delta_{3}(p,\lambda,b\\!\mid\\!s,\lambda)=0$ and
$\sigma\neq\lambda$.

We then obtain $e_{4}=2$.

(5) Finally, we set $M_{4}$ to be the desired 1ppda $N$. It is clear that $N$
satisfies all the requirements of the ideal-shape form. Thus, the proof of the
lemma is completed. $\Box$

It is important to note that the transformation of a general 1ppda to an
error-equivalent 1ppda in an ideal shape is quite costly in terms of stack-
state complexity. This high cost affects the overall cost of transforming one
endmarker 1ppda to another error-equivalent non-endmarker 1ppda.

Before closing this section, we give a short remark. Steps (3) and (4) in the
proof of Lemma 4.2 can be combined so that we can further remove any
$\lambda$-move by introducing a new set of instructions. More precisely, we
set a new transition function $\delta$ as a map from
$(Q-Q_{halt})\times\Sigma\times(\Gamma\cup{\cal P}(\Gamma-\\{Z_{0}\\})\times
Q\times\Gamma^{*}$ to $[0,1]$, where the notation
$\delta(q,\sigma,\\{a_{1},a_{2},\ldots,a_{k}\\}\\!\mid\\!p,\lambda)$ means
that we repeat the pop operation as long as the topmost stack symbols are in
$\\{a_{1},a_{2},\ldots,a_{k}\\}$ if possible (otherwise, we abort the
computation). For this $\delta$, we demand that
$\delta(q,\sigma,\\{a_{1},a_{2},\ldots,a_{k}\\}\\!\mid\\!p,u)>0$ implies
$u=\lambda$.

###  4.3 Usefulness of the Ideal-Shape Form

We have introduced to pushdown automata the notion of “ideal shape” form,
which controls the behaviors of push and pop operations of the pushdown
automata. To demonstrate the usefulness of this specific form in handling the
machines, we intend to present a simple and quick example of how to apply the
ideal-shape lemma (Lemma 4.2) for endmarker 1ppda’s.

###### Proposition 4.3

The family of all languages recognized by endmarker 1ppda’s with bounded-error
probability is closed under reversal.

###### Proof.

Let $L$ denote any language and let
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$
be any 1ppda that recognizes $L$ with bounded-error probability. By the ideal
shape lemma (Lemma 4.2), we can further assume that $M$ is in an ideal shape.
Hereafter, we construct another 1ppda
$N=(Q^{\prime},\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma^{\prime},\delta^{\prime},q^{\prime}_{0},Z_{0},Q^{\prime}_{acc},Q^{\prime}_{rej})$
that takes $x^{R}$ as an input and enters the same type of halting states as
$M$ does on the input $x$ with the same error probability. A basic idea of the
following construction is to reverse a computation of $M$ step by step by
probabilistically guessing the previous step of $M$ and by verifying the
validity of the guessing at the next step. If the guessing is incorrect, then
$N$ immediately enters both an accepting state and a rejecting state with the
equal probability to cancel out this incorrect guessing.

Formally, we set
$Q^{\prime}=(Q\times(\Sigma\cup\\{{|}\\!\\!\mathrm{c},\$\\}))\cup\\{q_{acc},q_{rej}\\}$,
$Q^{\prime}_{acc}=\\{q_{acc}\\}$, $Q^{\prime}_{rej}=\\{q_{rej}\\}$, and
$q^{\prime}_{0}=(q_{0},{|}\\!\\!\mathrm{c})$. A new probabilistic transition
function $\delta$ is defined as follows. Let
$\sigma,\tau\in\Sigma\cup\\{{|}\\!\\!\mathrm{c},\$\\}$. Let
$\delta^{\prime}((p,\tau),\tau,b\\!\mid\\!(q,\sigma),\lambda)=\delta(q,\sigma,a\\!\mid\\!p,b)$,
$\delta^{\prime}((p,\tau),\tau,c\\!\mid\\!(q,\sigma),a)=\delta(q,\sigma,a\\!\mid\\!p,\lambda)$,
$\delta^{\prime}((p,\sigma),\lambda,b\\!\mid\\!(q,\sigma),\lambda)=\delta(q,\lambda,a\\!\mid\\!p,b)$,
and
$\delta^{\prime}((p,\sigma),\lambda,c\\!\mid\\!(q,\sigma),a)=\delta(q,\lambda,a\\!\mid\\!p,\lambda)$.
In addition, for any halting state $\hat{p}\in\\{q_{acc},q_{rej}\\}$, we
define $\delta^{\prime}((q,\sigma),\tau,c\\!\mid\\!\hat{p},c)=1/2$ if
$\sigma\neq\tau$.

It is not difficult to show that, for each $\tau\in\\{acc,rej\\}$,
$p_{N,\tau}(x^{R})=p_{N,\tau}(x)$ holds for any input $x\in\Sigma^{*}$.
Therefore, $N$ correctly recognizes $L^{R}$ with bounded-error probability. ∎

##  5 From Endmarker 1ppda’s to No-Endmarker 1ppda’s

Following the preparatory steps of Section 4, let us prove Proposition 1.4.
The proof of this proposition is composed of several key ingredients, each of
which uses a different idea to place more restrictions on 1ppda’s. In
particular, the proof will proceed in three stages by firstly removing
${|}\\!\\!\mathrm{c}$ (Section 5.1), secondly removing the last series of
$\lambda$-moves after reading $\$$ (Section 5.2), and finally removing $\$$
(Section 5.3). In Section 5.4, we will combine these transformations and prove
a technical lemma (Lemma 5.5), from which Proposition 1.4 follows.

###  5.1 Removing the Left Endmarker

We begin with removing the left endmarker ${|}\\!\\!\mathrm{c}$ from the
1ppda’s input tape. What we need here is to construct a 1ppda without
${|}\\!\\!\mathrm{c}$, which simulates a given endmarker 1ppda. If we had made
the first set of moves “$\lambda$-moves”, then we could have easily simulated
the given machine. By our definition, however, any 1ppda cannot start with a
$\lambda$-move in order to simulate the machine with ${|}\\!\\!\mathrm{c}$.

For clarity, we call by a _no-left-endmarker 1ppda_ any 1ppda whose input tape
uses only the right endmarker and a tape head starts at the leftmost symbol,
instead of ${|}\\!\\!\mathrm{c}$, written on the input tape. In particular,
when the input is $\lambda$, the left-most symbol becomes $\$$.

###### Lemma 5.1

Let $M$ be any $n$-state 1ppda with stack alphabet size $m$. There is a 1ppda
$N$ that uses no left endmarker, has at most $2n$ states and at most $(n+1)m$
stack alphabet size, and is error-equivalent to $M$.

To obtain a precise stack-state complexity of transformation in Lemma 5.1, we
provide an explicit construction of the desired machine. A basic idea of the
construction of $N$ is to remember the leftmost input symbol while the target
machine $M$ reads ${|}\\!\\!\mathrm{c}$ and makes a (possible) series of
$\lambda$-moves.

Proof of Lemma 5.1.  We begin with a 1ppda
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$
equipped with the two endmarkers with $|Q|=n$, $|\Gamma|=m$, and push size
$e$. We want to construct its error-equivalent 1ppda $N$ that uses no left
endmarker ${|}\\!\\!\mathrm{c}$. We express $N$ as
$(Q^{\prime},\Sigma,\\{\$\\},\Gamma^{\prime},\Theta_{\Gamma^{\prime}},\delta^{\prime},\hat{q}_{0},Z_{0},Q^{\prime}_{acc},Q^{\prime}_{rej})$
and hereafter describe each component of $N$ in detail. Let
$x=x_{1}x_{2}\cdots x_{n}$ denote any input string of length $n$ over
$\Sigma$.

Let $\Gamma^{(-)}=\Gamma-\\{Z_{0}\\}$ and
$\Sigma_{\lambda}=\Sigma\cup\\{\lambda\\}$ and recall the notation
$[\Sigma,\Gamma]$ from Section 2.1. Define $Q^{\prime}=Q\cup\\{\hat{q}\mid
q\in Q\\}$, $\Gamma^{\prime}=\Gamma\cup[\Sigma,\Gamma]$, and
$\Theta_{\Gamma^{\prime}}=\Theta_{\Gamma}\cup[\Sigma,\Gamma]^{2}\cup[\Sigma,\Gamma]Z_{0}\cup[\Sigma,\Gamma]^{2}Z_{0}$.
We use the convention that, if $a=\lambda$, we set $[\sigma,a]$ to be
$\lambda$ for any $\sigma$. Clearly, $|Q^{\prime}|=2n$ and
$|\Gamma^{\prime}|=(n+1)m$ hold.

At the first step, $N$ must read the leftmost symbol $x_{1}$ of the string
$x\$$ written on the input tape. During this first step as well as its
(possible) subsequent $\lambda$-moves, $N$ takes the same steps as $M$ does on
${|}\\!\\!\mathrm{c}x_{1}$. For this purpose, $N$ needs to remember $x_{1}$ as
a part of its inner state until $M$ actually reads $x_{1}$ after making a
series of transitions (including $\lambda$-moves) related to
${|}\\!\\!\mathrm{c}$. In particular, while $M$ makes a $\lambda$-move, $N$
simulates this move without moving the tape head. Once $M$ reads $x_{1}$
completely, $N$ mimics $M$’s moves on $x_{1}$ without reading any new input
symbol.

The probabilistic transition function $\delta^{\prime}$ is formally given
below. Let $p,q\in Q$, $\sigma\in\Sigma$, $\xi\in\Sigma_{\lambda}$,
$a,b\in\Gamma$, $w\in\Gamma^{*}$, $k\in\mathbb{N}$, and
$a_{i}\in\Gamma^{(-)}\cup\\{\lambda\\}$ for all $i\in[k]$.

  1. 1.

$\delta^{\prime}(\hat{q}_{0},\sigma,Z_{0}\\!\mid\\!\hat{p},[\sigma,a_{k}]\cdots[\sigma,a_{1}][\sigma,Z_{0}]Z_{0})=\delta(q_{0},{|}\\!\\!\mathrm{c},Z_{0}\\!\mid\\!p,a_{k}\cdots
a_{1}Z_{0})$.

  2. 2.

$\delta^{\prime}(\hat{q}_{0},\$,Z_{0}\\!\mid\\!\hat{q},[\$,a_{k}]\cdots[\$,a_{1}][\$,Z_{0}]Z_{0})=\delta(q_{0},{|}\\!\\!\mathrm{c},Z_{0}\\!\mid\\!p,a_{k}\cdots
a_{1}Z_{0})$.

  3. 3.

$\delta^{\prime}(\hat{q},\lambda,[\sigma,b]\\!\mid\\!\hat{p},[\sigma,a_{k}]\cdots[\sigma,a_{1}][\sigma,b])=\delta(q,\lambda,b\\!\mid\\!p,a_{k}\cdots
a_{1}b)$ if $\delta[q,\lambda,b]>0$.

  4. 4.

$\delta^{\prime}(\hat{q},\lambda,[\sigma,b]\\!\mid\\!\hat{p},\lambda)=\delta(q,\lambda,b\\!\mid\\!p,\lambda)$
if $\delta[q,\lambda,b]>0$.

  5. 5.

$\delta^{\prime}(\hat{q},\lambda,[\sigma,b]\\!\mid\\!\hat{p},w)=\delta(q,\sigma,b\\!\mid\\!p,w)$
if $\delta[q,\lambda,b]=0$.

  6. 6.

$\delta^{\prime}(q,\xi,[\sigma,a]\\!\mid\\!p,w)=\delta(q,\xi,a\\!\mid\\!p,w)$.

  7. 7.

$\delta^{\prime}(q,\xi,a\\!\mid\\!p,w)=\delta(q,\xi,a\\!\mid\\!p,w)$.

Since $N$ begins with reading the leftmost symbol $x_{1}$ instead of
${|}\\!\\!\mathrm{c}$, we need to remember $x_{1}$ until $M$ actually reads
$x_{1}$ after making a series of transitions on ${|}\\!\\!\mathrm{c}$ (in Line
1–2). While $M$ makes a series of $\lambda$-moves, $N$ simulates them without
moving the tape head (in Line 3–4). After $M$ makes the last $\lambda$-move in
this series, $N$ simulates $M$’s move of reading $x_{1}$ (in Line 5). Once $M$
reads $x_{1}$, $N$ mimics $M$’s behavior step by step (in Line 6–7).

Note that Line 2 is needed to deal with the case of the empty input. Moreover,
Line 6 is needed because there are possibly bracketed symbols in the stack.
$\Box$

###  5.2 Removing the Final Series of $\lambda$-Moves

Next, let us consider a no-left-endmarker 1ppda
$M=(Q,\Sigma,\\{\$\\},\Gamma,\Theta_{\gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$.
Clearly, if $M$ enters halting states before reading the right endmarker $\$$
for all but finitely many inputs, then there is no trouble removing $\$$.
Hence, we hereafter assume that $M$ reaches $\$$ for infinitely many inputs.
Recall that, in our endmarker model, a 1ppda is permitted to make a series of
$\lambda$-moves even after reading the right endmarker $\$$. In the lemma
stated below, we wish to remove this final series of $\lambda$-moves and force
$M$ to halt immediately after reading $\$$. Furthermore, the lemma requires
the condition that a given 1ppda is in an ideal shape. This condition
guarantees that $M$ never makes any pop operation at reading $\$$ (not
including subsequent $\lambda$-moves).

###### Lemma 5.2

Let $M$ be any $n$-state 1ppda with stack alphabet size $m$ using no left
endmarker in an ideal shape. Assume that $M$ enters a halting state along any
computation path with a single accepting state (as well as a single rejecting
state) only after emptying the stack. There is an error-equivalent no-left-
endmarker 1ppda $P$ in an ideal shape that has at most $n(n+1)$ states and
stack alphabet size $m2^{n}$ but makes no $\lambda$-move after reading the
right endmarker $\$$.

Lemma 5.2 is the most essential part of our proof of Proposition 1.4. Our
proof of the lemma is inspired by [6, Lemma 2], in which Kaņeps, Geidmanis,
and Freivalds demonstrated how to convert each bounded-error unary 1ppda into
an equivalent bounded-error “inputless” 1ppda, where a _unary machine_ uses
only a unary input alphabet. Since our setting (including our assumption) is
different from [6, Lemma 2], we wish to provide the complete proof of the
lemma. A key idea of Kaņeps et. al. relies on a result of Nasu and Honda [9,
Section 6] regarding a certain property of _one-way probabilistic finite
automata_ (or 1pfa’s) on reversed inputs. In essence, for any given 1pfa $M$
with no $\lambda$-move, Nasu and Honda constructed another 1pfa $N$ that
accepts $x^{R}$ with the same probability as $M$ accepts $x$, assuming that we
carefully choose which inner states of $N$ to start and terminate.

Since $M$ is in an ideal shape, any $\lambda$-move must pop a stack symbol.
Thus, a series of pop operations (of the form
$\delta_{M}(q,\lambda,\sigma\\!\mid\\!p,\lambda)$) after reading $\$$ can be
seen as a series of probabilistic transitions consuming each stack symbol from
the topmost symbol to the bottom symbol. In other words, this process is
completely described as an appropriate 1pfa taking a stack content as its
input and making no $\lambda$-move. Such a 1pfa is described as
$N=(Q,\Gamma^{(-)},\\{Z_{0}\\},\delta_{N})$ _with neither initial state nor
halting states_ , where $\Gamma^{(-)}$ is used as an input alphabet, $Z_{0}$
is treated as a new right endmarker, and
$\delta_{N}(q,\sigma\\!\mid\\!p)=\delta_{M}(q,\lambda,\sigma\\!\mid\\!p,\lambda)$
for any tuple $(p,q,\sigma)$. Notice that $\Gamma^{(-)}\cup\\{Z_{0}\\}$
coincides with $\Gamma$. We force $N$ to run until $Z_{0}$ is completely read.
For our convenience, we call such a machine a _free 1pfa_. Given such a free
1pfa $N$, the notation $p_{N}(q,w,p)$ denotes the probability that $N$ starts
in inner state $q$, reads $w$ completely, and then enters inner state $p$.
Formally, for any $w=w_{1}w_{2}\cdots
w_{n}\in(\Gamma^{(-)})^{*}\cup(\Gamma^{(-)})^{*}Z_{0}$, $p_{N}(q,w,p)$ is
defined to be $\sum_{p_{2},\ldots,p_{n}\in
Q}(\prod_{i\in[n]}\delta_{N}(p_{i},w_{i}\\!\mid\\!p_{i+1}))$ with $p_{1}=q$
and $p_{n+1}=p$.

The acceptance/rejection probability of $M$ on input $x$ is given by the
probability distribution produced by $M$ after completely reading $x\$$
(without making $\lambda$-moves after reading $\$$) multiplied by the
probability of $N$’s processing (as its own input) the stack content generated
by $M$ on $x\$$. However, to simulate $N$ properly, we need to read the stack
content of $M$ from the bottom symbol to the top symbol: the “reverse” of the
input given to $N$. What we need for the construction of the desired 1ppda $P$
in Lemma 5.2 is a free 1pfa $K$ that simulates $N$ on input $x$ but $K$ reads
the reverse of $x$.

We thus introduce a supportive lemma, stated as Lemma 5.3. This lemma ensures
that we can construct a free 1pfa $K$ that “mimics” the behavior of a given
1pfa $M$ by reading a “reversed” input if we choose appropriate inner states
to start and terminate.

###### Lemma 5.3

Take $N$ and $p_{N}$ that are constructed from $M$ as above. There exists a
free 1pfa $K=(Q_{K},\Gamma^{(-)},\\{Z_{0}\\},\delta_{K})$ with
$|Q_{K}|=2^{|Q|}$ that satisfies the following: for any pair $p,q\in Q$, there
exist an inner state $s(p)\in Q_{K}$ and a set $T(q)\subseteq Q_{K}$
satisfying $p_{N}(q,w,p)=\sum_{r\in T(q)}p_{K}(s(p),w^{R},r)$ for any
$w\in(\Gamma^{(-)})^{*}\cup(\Gamma^{(-)})^{*}Z_{0}$, where $p_{K}$ is defined
from $K$ similarly to $p_{N}$.

Our proof of Lemma 5.3 closely follows the proof of Nasu and Honda [9, Theorem
6.1] in order to construct the desired $K$. For this purpose, we first
reformulate a computation of $N$ in a more traditional way using a set of
_transition matrices_ instead of the transition function $\delta_{N}$. Given a
symbol $\sigma\in\Gamma^{(-)}$, we write
$U_{\sigma}=(a_{p,q}^{(\sigma)})_{p,q\in Q}$ for a transition matrix obtained
by setting $a_{p,q}^{(\sigma)}=\delta_{N}(p,\sigma\\!\mid\\!q)$. Given an
inner state $q\in Q$, $\pi_{q}$ denotes a row vector in which each entry
indexed by $r$ is $1$ if $r=q$ and $0$ otherwise. It then follows that
$p_{N}(q,w\\!\mid\\!p)=\pi_{q}U_{w}\pi_{p}^{T}$, where $U_{w}$ is the matrix
multiplication $U_{w_{1}}U_{w_{2}}\cdots U_{w_{n}}$ if $w=w_{1}w_{2}\cdots
w_{n}$ for $w_{1},w_{2},\ldots,w_{n}\in\Gamma^{(-)}$. Notice that
$p_{N}(q,w,p)$ also equals $(\pi_{q}U_{w}\pi_{p}^{T})^{T}$, which is simply
$\pi_{p}U_{w}^{T}\pi_{q}^{T}$. Thus, the transpose $U_{w}^{T}$ can “simulate”
$N$ on $w$ by reading its reverse $w^{R}$. It therefore suffices to construct
a stochastic matrix $V_{w}$ that produces the same acceptance/rejection
distribution as $U_{w}^{T}$. However, since the transpose $U_{w}^{T}$ may not
be stochastic in general, we need to expand the original vector space used for
$U_{w}^{T}$ to a much larger vector space. Using a construction similar to
Nasu and Honda’s, we then build the desired $K$ from $N$.

Proof of Lemma 5.3.  Let
$M=(Q,\Sigma,\\{\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$
be a no-left-endmarker 1ppda in an ideal shape and
$N=(\Theta,\Gamma^{(-)},\\{Z_{0}\\},\delta_{N})$. Let the new notation $[x\in
A]$ denote the _truth value_ of the statement “$x\in A$”; namely, $[x\in A]$
equals $1$ if $x\in A$, and $0$ otherwise. Let $n=|Q|$. For readability,
without loss of generality, we identify $Q$ with the integer set $[n]$ with
$q_{0}=0$. We then set $Q_{K}={\cal P}(Q)$ and express $Q_{K}$ as
$\\{Q_{1},Q_{2},\ldots,Q_{2^{n}}\\}$ with $Q_{1}=\varnothing$ and
$Q_{2^{n}}=Q$. For each symbol $\sigma\in\Gamma^{(-)}$, we abbreviate
$\delta_{N}(i,\sigma\\!\mid\\!j)$ as define $\alpha^{(\sigma)}_{ij}$ for each
pair $i,j\in Q$ and consider the transition matrix
$U_{\sigma}=(\alpha_{ij}^{(\sigma)})_{i,j\in Q}$ of $N$ associated with
$\sigma$. Moreover, we set $\pi_{i}=(\pi_{i1},\pi_{i2},\ldots,\pi_{in})$ with
$\pi_{ii}=1$ and $\pi_{ij}=0$ for any distinct pair $i,j\in Q$. Given any
index $j\in Q$, we express the $j$th row
$(\alpha_{j1}^{(\sigma)},\ldots,\alpha_{jn}^{(\sigma)})$ of $U_{\sigma}$ as
$\alpha_{j}(\sigma)$. Note that
$p_{N}(i,w,j)=\pi_{i}U_{w}\pi_{j}^{T}=(\pi_{i}U_{w}\pi_{j}^{T})^{T}=\pi_{j}U_{w}^{T}\pi_{i}^{T}$.
Since $U_{w}^{T}=U_{w_{n}}^{T}U_{w_{n-1}}^{T}\cdots U_{w_{1}}^{T}$, it
suffices to define a matrix $V_{\sigma}$ that “simulates” $U_{\sigma}^{T}$ for
every symbol $\sigma$.

In what follows, we intend to define
$V_{\sigma}=(\gamma_{kl}^{(\sigma)})_{k,l\in[2^{n}]}$ from $U_{\sigma}^{T}$.
Let $\gamma_{k}(\sigma)$ denote the $k$th row of $V_{\sigma}$ and assume that
$\gamma_{k}(\sigma)$ has the form
$(\gamma_{k1}^{(\sigma)},\gamma_{k2}^{(\sigma)},\ldots,\gamma_{k2^{n}}^{(\sigma)})$
for each index $k\in[2^{n}]$. To define $\gamma_{k}(\sigma)$, we need to
consider the supportive vector $\beta_{k}(\sigma)=\sum_{j\in
Q_{k}}\alpha_{j}(\sigma)$. For later use, we express $\beta_{k}(\sigma)$ as
$(\beta_{k1}^{(\sigma)},\beta_{k2}^{(\sigma)},\ldots,\beta_{kn}^{(\sigma)})$.

As our preparation, we introduce two extra notations for each index
$k\in[2^{n}]$: (1) $\min(\beta_{k}(\sigma))$ denotes the minimum positive
value of any entry of the vector $\beta_{k}(\sigma)$ (if one exists), namely,
$\min\\{\beta^{(\sigma)}_{kj}\mid j\in[n],\beta^{(\sigma)}_{kj}>0\\}$, (2)
$\max(\beta_{k}(\sigma))$ denotes the maximum value of any entry of
$\beta_{k}(\sigma)$, and (3) $e_{k}$ denotes the $\\{0,1\\}$-vector $([1\in
Q_{k}],[2\in Q_{k}],\ldots,[n\in Q_{k}])$. In particular, since
$Q_{1}=\varnothing$ and $Q_{2^{n}}=Q$, we obtain $e_{1}=(0,0,\ldots,0)$ and
$e_{2^{n}}=(1,1,\ldots,1)$.

Fix $k\in[2^{n}]$ arbitrarily. Inductively, we construct a series of
supportive vectors
$\hat{\beta}_{k}^{(1)}(\sigma),\hat{\beta}_{k}^{(2)}(\sigma),\ldots$ as
follows. Initially, we set $\hat{\beta}_{k}^{(1)}(\sigma)=\beta_{k}(\sigma)$.
Given an index $i\in[n-1]$, $\hat{\beta}_{k}^{(i)}(\sigma)$ is assumed to have
already been defined. If $\hat{\beta}_{k}^{(i)}(\sigma)={\bf 0}$, then we stop
the construction process. Assume otherwise. Let
$\hat{\beta}_{k}^{(i)}(\sigma)=(\tilde{\beta}_{1}^{(i)},\tilde{\beta}_{2}^{(i)},\ldots,\tilde{\beta}_{n}^{(i)})$.
We choose an index $m(i)\in[2^{n}]$ for which $Q_{m(i)}$ equals
$\\{j\in[n]\mid\tilde{\beta}_{j}^{(i)}>0\\}$. We then define
$\gamma_{km(i)}^{(\sigma)}=\min(\hat{\beta}_{k}^{(i)}(\sigma))$ and
$\hat{\beta}_{k}^{(i+1)}(\sigma)=\hat{\beta}_{k}^{(i)}(\sigma)-\gamma_{km(i)}^{(\sigma)}\cdot
e_{m(i)}$. Assume that the construction process terminates after $t$ steps.
Note that $1\leq t\leq n$ holds. After the process terminates, we set
$\gamma_{k1}^{(\sigma)}=1-\max(\beta_{k}(\sigma))$ and
$\gamma_{kl}^{(\sigma)}=0$ for any $l\in[2^{n}]$ that are yet undefined. Since
$\sum_{i\in[t]}\min(\hat{\beta}_{k}^{(i)}(\sigma))=\sum_{j\in[n]}\beta_{kj}^{(\sigma)}=\max(\beta_{k}(\sigma))$,
it follows that
$\sum_{l\in[2^{n}]}\gamma_{kl}^{(\sigma)}=\gamma_{k1}^{(\sigma)}+\sum_{i\in[t]}\min(\hat{\beta}_{k}^{(i)}(\sigma))=\gamma_{k1}^{(\sigma)}+\max(\beta_{k}(\sigma))=1$.
Thus, $V_{\sigma}$ is stochastic. We further define
$\hat{\pi}_{k}=(\hat{\pi}_{k1},\hat{\pi}_{k2},\ldots,\hat{\pi}_{k2^{n}})$ by
setting $\hat{\pi}_{kk}=1$ and $\hat{\pi}_{kl}=0$ for any distinct pair
$k,l\in[2^{n}]$.

Finally, we set $\delta_{K}(Q_{k},\sigma\\!\mid\\!Q_{l})$ to be
$\gamma^{(\sigma)}_{kl}$ for any $k,l\in[2^{n}]$. Notice that
$p_{K}(Q_{k},w^{R},Q_{l})=\hat{\pi}_{k}V_{w^{R}}\hat{\pi}_{l}^{T}$, where
$V_{w^{R}}=V_{w_{n}}V_{w_{n-1}}\cdots V_{w_{1}}$. Furthermore, we set
$s(j)=\\{j\\}\in Q_{K}$ and $T(i)=\\{A\in Q_{K}\mid i\in A\\}$. The desired
equality $p_{N}(i,w,j)=\sum_{r\in T(i)}p_{K}(s(j),w^{R},r)$ comes from the
above definition of $K$. Note that $|Q_{K}|=|{\cal P}(Q)|=2^{|Q|}$. $\Box$

Let us return to Lemma 5.2 and provide its proof with the help of Lemma 5.3.

Proof of Lemma 5.2.  Let
$M=(Q,\Sigma,\\{\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$
be any no-left-endmarker 1ppda in an ideal shape with $Q_{acc}=\\{q_{acc}\\}$
and $Q_{rej}=\\{q_{rej}\\}$. Our goal is to remove all $\lambda$-moves made by
$M$ after reading $\$$. Associated with the machine $M$, we take a free 1pfa
$K=(Q_{K},\Gamma^{(-)},\\{Z_{0}\\},\delta_{K})$ and functions $s(\cdot)$,
$T(\cdot)$, and $p_{K}(\cdot)$ satisfying Lemma 5.3. Remember that $K$ can
mimic a series of $\lambda$-moves of $M$ by an appropriate choice of inner
states and that $K$ starts in initial state $q^{\prime}_{0}=s(q_{acc})$.

Let
$P=(Q^{\prime},\Sigma,\\{\$\\},\Gamma^{\prime},\Theta_{\Gamma^{\prime}},\delta^{\prime},q^{\prime}_{0},Z_{0},Q_{acc},Q_{rej})$
denote the desired 1ppda by which we want to simulate $M$ as well as $K$. The
machine $P$ needs to remember both inner states of $M$ and $K$ in the form of
$(q,q^{\prime})$ during the intended simulation. When $M$ pushes a stack
symbol, $P$ simulates its move and, simultaneously, it runs $K$ on this pushed
symbol. Since $K$ uses a different set of inner states, we need to remember
the changes of such states in its own stack. A stack symbol of the form
$[a,r]$ indicates that $K$ is in inner state $r$ reading $a$.

Formally, we set $q^{\prime}_{0}=s(q_{acc})$,
$\Gamma^{\prime}=[\Gamma,Q_{K}]$, $Q^{\prime}=Q\times Q_{K}$,
$Q^{\prime}_{acc}=\\{(p,p^{\prime})\in Q^{\prime}\mid p^{\prime}\in T(p)\\}$,
and $Q^{\prime}_{rej}=Q^{\prime}-Q^{\prime}_{acc}$. It then follows that
$|Q^{\prime}|\leq n+n^{2}=n(n+1)$ and
$|\Gamma^{\prime}|=|\Gamma||Q_{K}|=m2^{n}$. The probabilistic transition
function $\delta^{\prime}$ is constructed to satisfy the following conditions.
We wish to define $\delta^{\prime}$ in stages (1)–(3). Let $p,q\in Q$,
$p^{\prime},q^{\prime}\in Q_{K}$, $a,b\in\Gamma$, and
$\sigma\in\Sigma\cup\\{\lambda\\}$.

(1) The initial transition of $\delta^{\prime}$ is defined as follows. Recall
that the first step of $M$ cannot be a $\lambda$-move.

  1. 1.

$\delta^{\prime}((q_{0},q^{\prime}_{0}),\sigma,Z_{0}\\!\mid\\!(p,p^{\prime}),[Z_{0},q^{\prime}_{0}]Z_{0})=\delta(q_{0},\sigma,Z_{0}\\!\mid\\!p,Z_{0})\delta_{K}(q^{\prime}_{0},Z_{0}\\!\mid\\!p^{\prime})$
if $\sigma\neq\lambda$.

  2. 2.

$\delta^{\prime}((q_{0},q^{\prime}_{0}),\sigma,Z_{0}\\!\mid\\!(p,p^{\prime}),[b,q^{\prime}_{0}]Z_{0})=\delta(q_{0},\sigma,Z_{0}\\!\mid\\!p,bZ_{0})p_{K}(q^{\prime}_{0},Z_{0}b,p^{\prime})$
if $\sigma\neq\lambda$.

(2) Consider the case where $M$ is in state $q$ reading input symbol $\sigma$
and stack symbol $a$ and $P$ is in state $(q,q^{\prime})$ reading stack symbol
$[a,r]$. If $M$ pushes $b$ into the stack and $K$ is in inner state
$q^{\prime}$ reading $[a,r]$ associated with $a$ (Line 3), then $P$ enters
$(p,p^{\prime})$ and pushes $[b,q^{\prime}]$ with the same probability
multiplied by the extra probability that $K$ processes $b$ and enters
$p^{\prime}$ from $q^{\prime}$. It is important to remember the inner state
$q^{\prime}$ of $K$ in the stack. If $M$ does not change the topmost stack
symbol $a$ (Line 4), then $P$ only changes $(q,q^{\prime})$ to
$(p,q^{\prime})$ since we do not need to simulate $K$’s step.

  1. 3.

$\delta^{\prime}((q,q^{\prime}),\sigma,[a,r]\\!\mid\\!(p,p^{\prime}),[b,q^{\prime}][a,r])=\delta(q,\sigma,a\\!\mid\\!p,ba)\delta_{K}(q^{\prime},b\\!\mid\\!p^{\prime})$
for $\sigma\in\Sigma\cup\\{\$\\}$ if $\sigma\neq\lambda$.

  2. 4.

$\delta^{\prime}((q,q^{\prime}),\sigma,[a,r]\\!\mid\\!(p,q^{\prime}),[a,r])=\delta(q,\sigma,a\\!\mid\\!p,a)$
if $\sigma\neq\lambda$.

(3) In contrast to (2), if $M$ pops $a$, then we need to “cancel out” the
probability that $K$ processes $a$ in state $r$. This is a crucial process in
our simulation. If $K$ is a reversible machine, we can easily reverse the
computation to nullify the effect of $\delta_{K}$ at the previous step. Since
$K$ is generally not a reversible machine, nonetheless, we must remember the
previous inner state $r$ and force $K$ to roll back to $r$. For this purpose,
$P$ makes the following move.

  1. 5.

$\delta^{\prime}((q,q^{\prime}),\sigma,[a,r]\\!\mid\\!(p,r),\lambda)=\delta(q,\sigma,a\\!\mid\\!p,\lambda)$.

When $M$ pops symbol $a$ (in Line 5), $P$ also pops $[a,r]$ with the same
probability but rolls back the inner state of $K$ from $q^{\prime}$ to its
previous state $r$ to cancel out the probability that $K$ processes $a$ in
state $r$ and enters $q^{\prime}$.

(4) Assume that $M$ has already produced a stack content of the form $wZ_{0}$
and $M$ is now reading $\$$. Notice that, by this moment, $P$ must have
already finished the simulation of $K$ on the input $(wZ_{0})^{R}$. Recall
that $K$ provides the acceptance/rejection probability that $M$ makes a
(possible) series of consecutive $\lambda$-moves after reading $\$$. When $M$
pops symbol $a$ with a certain probability at reading $\$$, $P$ also pops
$[a,r]$ with the same probability.

  1. 6.

$\delta^{\prime}((q,q^{\prime}),\$,[a,r]\\!\mid\\!(p,p^{\prime}),[b,q^{\prime}][a,r])=\delta(q,\$,a\\!\mid\\!p,ba)\delta_{K}(q^{\prime},b\\!\mid\\!p^{\prime})$.

  2. 7.

$\delta^{\prime}((q,q^{\prime}),\$,[a,r]\\!\mid\\!(p,q^{\prime}),[a,r])=\delta(q,\$,a\\!\mid\\!p,a)$.

Lines 6–7 clearly guarantee that, after reading $\$$, $P$ does not make any
$\lambda$-move.

By the above definition of $\delta^{\prime}$, it is not difficult to show that
$P$ correctly simulates $M$ with the same error probability. We remark that
$P$ is also in an ideal shape. $\Box$

###  5.3 Removing the Right Endmarker

Throughout Sections 5.1–5.2, we have constructed 1ppda’s that neither have the
left endmarker nor makes any $\lambda$-move after reading the right endmarker
$\$$. Let $M$ be any of those 1ppda’s equipped with only the right endmarker
$\$$. In this final stage of our construction toward Proposition 1.4, we
further remove $\$$ from $M$. Notice that, without the endmarker $\$$, the
1ppda’s cannot in general empty their stacks before halting.

###### Lemma 5.4

Let $M$ be any $n$-state 1ppda in an ideal shape with stack alphabet size $m$
but using no left endmarker, and assume that there is no $\lambda$-move after
reading $\$$. Moreover, we assume that $M$ does not alter the stack content at
reading $\$$. There exists an error-equivalent 1ppda $N$ with no endmarker
using $2n+1$ states and stack alphabet size $(n+1)m$.

We briefly remark on our proof strategy for Lemma 5.4. Assume that we are
reading an input symbol. We first simulate the corresponding move of $M$. We
then predict an encounter of $\$$ at the next move and, based on that
prediction, we simulate the transition of $M$ taken at reading $\$$. In the
next step, if the next input symbol is indeed $\$$ as we have predicted, then
we immediately decide either “accept” or “reject” according to the current
inner state. Otherwise, since our prediction is incorrect, we need to
probabilistically “nullify” the simulation of the last move on $\$$ and
probabilistically simulate the next move of $M$. We continue the simulation
until $M$ actually encounters $\$$. If we try to probabilistically “rewind”
the simulation of the last transition of $M$ on $\$$ by taking a strategy of
nondeterministically choosing the previous inner state and reversing the last
transition of $M$, then the resulting error probability may differ from the
original one. Thus, we cannot take this simple strategy in the following
proof.

Proof of Lemma 5.4.  Let
$M=(Q,\Sigma,\\{\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$
be any 1ppda in an ideal shape with no left endmarker. We assume that, on all
inputs, $M$ makes no $\lambda$-move right after reading $\$$ and, more
importantly, $M$ does not alter any stack content at reading $\$$. Note that,
when reading $\$$ at the final move, $M$ must make the final decision of
whether it accepts or rejects an input without changing the stack content. To
eliminate this final move, we must generate the transition probability of this
particular move _without reading $\$$_. This last transition must be of the
form $\delta(p,\$,a\\!\mid\\!r,a)$ for a certain triplet $(p,r,a)$ and we call
this value $\delta(p,\$,a\\!\mid\\!r,a)$ the _decision probability_ at
$(p,r,a)$. Notice that $\sum_{r\in Q}\delta(p,\$,a\\!\mid\\!r,a)=1$ holds
because $M$ does not make any $\lambda$-move in inner state $p$ reading $\$$.
Our goal is to define a new no-endmarker machine
$N=(Q^{\prime},\Sigma,\Gamma^{\prime},\Theta_{\Gamma^{\prime}},\delta^{\prime},q^{\prime}_{0},Z_{0},Q^{\prime}_{acc},Q^{\prime}_{rej})$
that simulates $M$ with the same error probability. Hereafter, we explain how
to construct the desired machine $N$.

Concerning the key elements $Q^{\prime}_{acc}$ and $Q^{\prime}_{rej}$ of $N$,
we set $Q^{\prime}_{acc}=Q_{acc}\cup\\{q_{0}\\}$ and
$Q^{\prime}_{rej}=Q_{rej}$ if $\lambda\in L(M)$, and
$Q^{\prime}_{acc}=Q_{acc}$ and $Q^{\prime}_{rej}=Q_{rej}\cup\\{q_{0}\\}$
otherwise. We further define $Q^{\prime}=Q\cup\\{p^{(+)}\mid p\in Q\\}$ and
$\Gamma^{\prime}=\Gamma\cup[Q,\Gamma]$. Note that $|Q^{\prime}|=2n+1$ and
$|\Gamma^{\prime}|=m+nm=m(n+1)$. To simulate the first step of $M$, assuming
that the next step is the final step, we produce the decision probability
associated with this final step. Since this assumption may be false, we need
to remember the assumed final move using the stack. At every step, we first
cancel out the decision probability taken at the previous step by simply
“ignoring” the assumed final step (i.e., summing up all the possible final
steps) to nullify the previously-taken final step. After nullifying the
supposed final step, we apply a new probabilistic transition and produce the
next decision probability. To recover the previous decision probability, since
the computation is not in general reversible, we need to remember a triplet
$(p,r,a)$. This process is formally expressed as follows. Let
$\sigma\in\Sigma$ and $p\in Q$.

  1. 1.

$\delta^{\prime}(q_{0},\sigma,Z_{0}\\!\mid\\!p,[r,Z_{0}]Z_{0})=\delta(q_{0},\sigma,Z_{0}\\!\mid\\!p,Z_{0})\delta(p,\$,Z_{0}\\!\mid\\!r,Z_{0})$.

  2. 2.

$\delta^{\prime}(q_{0},\sigma,Z_{0}\\!\mid\\!p,[r,a]Z_{0})=\delta(q_{0},\sigma,Z_{0}\\!\mid\\!p,aZ_{0})\delta(p,\$,a\\!\mid\\!r,a)$
if $a\in\Gamma^{(-)}$.

In inner state $q$, $N$’s topmost stack symbol $[r,a]$ indicates that the last
applied transition is of the form $\delta(p,\$,a\\!\mid\\!r,a)$ for an inner
state $p$ that entered from $q$ in a single step.

For instance, from Line 1, it follows that $\sum_{r\in
Q}\delta^{\prime}(q_{0},\sigma,Z_{0}\\!\mid\\!p,[r,Z_{0}]Z_{0})=\sum_{r\in
Q}\delta(q_{0},\sigma,Z_{0}\\!\mid\\!p,Z_{0})\delta(p,\$,Z_{0}\\!\mid\\!r,Z_{0})=\delta(q_{0},\sigma,Z_{0}\\!\mid\\!p,Z_{0})\sum_{r\in
Q}\delta(p,\$,Z_{0}\\!\mid\\!r,Z_{0})=\delta(q_{0},\sigma,Z_{0}\\!\mid\\!p,Z_{0})$.
Therefore, if $N$ takes all inner states $r$ into consideration, it can cancel
out the probability $\delta(p,\$,Z_{0}\\!\mid\\!r,Z_{0})$ from its
computation. A similar result follows from Line 2. We generalize this argument
as follows. We denote by $\mu_{M}(q,x,a\>\|\>p,w)$ the probability that $M$
starts in inner state $q$ with a topmost stack symbol $a$, reads input $x$
completely, and reaches inner state $p$ with stack content $w$. Similarly,
$\mu_{N}$ is defined using $N$. We want to enforce the following condition
between $\mu_{M}$ and $\mu_{N}$.

> Condition (*):
> $\mu_{N}(q_{0},x,Z_{0}\>\|\>p,[r,a]w)=\mu_{M}(q_{0},x,Z_{0}\>\|\>p,aw)\delta(p,\$,a\\!\mid\\!r,a)$
> holds for an appropriately chosen quintuple $(p,x,r,a,w)$ with
> $x\neq\lambda$.

From Condition (*), it follows that
$\mu_{M}(q_{0},x\$,Z_{0}\>\|\>p,aw)=\sum_{r\in
Q}\mu_{N}(q_{0},x,Z_{0}\>\|\>p,aw)\delta(p,\$,a\\!\mid\\!r,a)=\sum_{r\in
Q}\mu_{N}(q_{0},x,Z_{0}\>\|\>p,[r,a]w)$. This equation makes it possible to
“nullify” the previously taken probability $\delta(p,\$,a\\!\mid\\!r,a)$ out
of the computation of $N$ by “ignoring” the choice of $r$ made at the previous
step.

Assuming that Condition (*) is true, when $N$ reads off the entire input $x$,
$N$ accepts and rejects $x$ with the same error probability as $M$ does. More
precisely, if $M$ halts with probability $\gamma$ reaching state $r$ with
stack content $aw$, then $\gamma$ equals
$\mu_{M}(q_{0},x,Z_{0}\>\|\>p,aw)\delta(p,\$,a\\!\mid\\!r,a)$, and thus $N$
halts in inner state $p$ with probability $\gamma$.

In Lines 3–6 shown below, we follow the convention that, when either
$\delta(q,\$,a\\!\mid\\!r,a)=0$ or $\delta(q,\$,Z_{0}\\!\mid\\!r,Z_{0})=0$,
the left sides of the corresponding equations must take value $0$. Let
$\sigma\in\Sigma_{\lambda}$, $a,b\in\Gamma$, $p,q\in Q$, and $w\in\Gamma^{*}$.
If $M$ pushes $bw$ on the top of stack symbol $a$, we remember $w$ and place
$[s,b]$ on the top of the stack (in Line 3).

  1. 3.

$\delta^{\prime}(q,\sigma,[r,a]\\!\mid\\!p,[s,b]w)=\delta(q,\sigma,a\\!\mid\\!p,bw)\delta(p,\$,b\\!\mid\\!s,b)$
if $b\in\Gamma^{(-)}$ and $w\in(\Gamma^{(-)})^{*}$.

  2. 4.

$\delta^{\prime}(q,\sigma,[r,a]\\!\mid\\!p,[s,b])=\delta(q,\sigma,a\\!\mid\\!p,b)\delta(p,\$,b\\!\mid\\!s,b)$
if $a\in\Gamma^{(-)}\cup\\{\lambda\\}$ and $\sigma\neq\lambda$.

  3. 5.

$\delta^{\prime}(q,\sigma,[r,Z_{0}]\\!\mid\\!p,[s,Z_{0}])=\delta(q,\sigma,Z_{0}\\!\mid\\!p,Z_{0})\delta(p,\$,Z_{0}\\!\mid\\!s,Z_{0})$
if $\sigma\neq\lambda$.

When $M$ pops $a$, $N$ cancels out the previous decision probability, pops
$[r,a]$ instead, replaces any new topmost symbol, say, $b$ by $[s,b]$, and
multiplies the corresponding decision probability (Lines 6–7).

  1. 6.

$\delta^{\prime}(q,\sigma,[r,a]\\!\mid\\!p^{(+)},\lambda)=\delta(q,\sigma,a\\!\mid\\!p,\lambda)$
if $a\in\Gamma^{(-)}$.

  2. 7.

$\delta^{\prime}(p^{(+)},\lambda,b\\!\mid\\!p,[s,b])=\delta(p,\$,b\\!\mid\\!s,b)$.

  3. 8.

$\delta^{\prime}(q,\sigma,d\\!\mid\\!p,e)=0$ for all the other tuples
$(q,\sigma,d,p,e)$.

Note that, by our definition,
$\delta^{\prime}(q,\sigma,[r,Z_{0}]\\!\mid\\!p,\lambda)=0$ holds for any
$(q,\sigma,p)$. If Condition (*) is true, then $\delta^{\prime}$ correctly
simulates $\delta$ until $\$$ is read.

To complete the proof, we still need to verify Condition (*). We want to prove
it by induction on the length of nonempty input $x$. If $|x|=1$, then Lines
1–2 and 6–7 with $\sigma=\lambda$ imply Condition (*). Consider the case where
our input is of the form $x\sigma$ for $\sigma\in\Sigma$. In this case, the
value $\mu_{M}(q_{0},x\sigma,Z_{0}\>\|\>p,bw)$ with $\sigma\in\Gamma^{(-)}$ is
the sum of the following terms, over all $q\in Q$, ($a$)
$\mu_{M}(q_{0},x,Z_{0}\>\|\>q,aw)\delta(q,\sigma,a\\!\mid\\!p,b)$, ($b$)
$\mu_{M}(q_{0},x,Z_{0}\|q,av)\delta(q,\sigma,a\\!\mid\\!p,bu)$ with $w=uv$,
and ($c$)
$\mu_{M}(q_{0},x,Z_{0}\>\|\>q,abw)\delta(q,\sigma,a\\!\mid\\!p,\lambda)$. By
induction hypothesis, we obtain
$\mu_{N}(q_{0},x,Z_{0}\>\|\>p,[r,a]w)=\mu_{M}(a_{0},x,Z_{0}\>\|\>q,aw)\delta(p,\$,a\\!\mid\\!r,a)$.
Next, we calculate $\mu_{N}(q_{0},x\sigma,Z_{0}\>\|\>q,[t,b]w)$. Here, we
focus on term ($a$), provided that the corresponding step of $\delta^{\prime}$
is given by Line 4. It follows that, since $\sum_{r\in
Q}\delta(p,\$,q\\!\mid\\!r,a)=1$,

$\displaystyle\sum_{r\in
Q}\mu_{N}(q_{0},x,Z_{0}\>\|\>q,[r,a]w)\delta^{\prime}(q,\sigma,[r,a]\\!\mid\\!p,[t,b])$
$\displaystyle=$ $\displaystyle\sum_{r\in
Q}\mu_{M}(q_{0},x,Z_{0}\>\|\>q,aw)\delta(p,\$,a\\!\mid\\!r,a)\delta(q,\sigma,p,b)\delta(p,\$,b\\!\mid\\!s,b)$
$\displaystyle=$
$\displaystyle\mu_{M}(q_{0},x,Z_{0}\>\|\>q,aw)\delta(q,\sigma,p,b)\delta(p,\$,b\\!\mid\\!s,b)\cdot\sum_{r\in
Q}\delta(p,\$,a\\!\mid\\!r,a)$ $\displaystyle=$
$\displaystyle\mu_{M}(q_{0},x\sigma,Z_{0}\>\|\>q,bw)\delta(p,\$,b\\!\mid\\!s,b).$

The other terms ($b$)–($c$) are in essence similarly handled. Therefore,
Condition (*) is true, as requested. $\Box$

###  5.4 Proof of Proposition 1.4

Let us combine all transformations constructed in Sections 5.1–5.3 together
with Section 4 to form the complete proof of Proposition 1.4. The proposition
is actually an immediate consequence of a more technical lemma (Lemma 5.5). We
thus intend to verify the lemma in this subsection.

###### Lemma 5.5

Given an $n$-state endmarker 1ppda with stack alphabet size $m$ and push size
$e$, there is an error-equivalent no-endmarker 1ppda with
$O(e^{2}n^{4}m^{4}(2m)^{3enm})$ states, stack alphabet size
$O(e^{3}n^{6}m^{6}(2m)^{5enm}2^{t})$, and push size $1$, where
$t=2en^{2}m^{2}(2m)^{2enm}$.

###### Proof.

The proof of the lemma begins with taking an arbitrary 1ppda
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\delta,q_{0},Z_{0},Q_{acc},Q_{rej})$
with the two endmarkers. Let $|Q|=n$ and $|\Gamma|=m$. We apply Lemmas 4.1–4.2
and then obtain a 1ppda $M_{1}$ in an ideal shape with $Q_{1}$ and
$\Gamma_{1}$ satisfying that $|Q_{1}|\leq 24en^{2}m^{2}(2m)^{2enm}$ and
$|\Gamma_{1}|\leq 2enm(2m)^{2enm}$. We then apply Lemmas 5.1–5.4 sequentially.
Finally, we obtain a no-endmarker 1ppda $M_{2}$ with
$|Q_{2}|=O(e^{2}n^{4}m^{4}(2m)^{3enm})$ and
$|\Gamma_{2}|=O(e^{3}n^{6}m^{6}(2m)^{5enm}2^{t})$, where
$t=2en^{2}m^{2}(2m)^{2enm}$.

This completes the proof of the lemma. ∎

##  6 Quick Conclusion and Open Problems

Two different formulations have been used in textbooks and scientific papers
to describe various models of pushdown automata in the past: pushdown automata
_with two endmarkers_ and those _with no endmarkers_. These two formulations
have been well-known to be “equivalent” in recognition power for the
deterministic and the nondeterministic models of one-way pushdown automata.
Concerning the probabilistic model, the past literature [8, 4, 15, 16] used
both formulations to obtain structural properties of pushdown automata but no
proof of the “equivalence” between the two formulations (stated as the _no
endmarker theorem_) has been published yet so far. This paper has given the
formal proof of converting between the two formalisms and, more importantly,
it has provided the first explicit upper bound on the stack-state complexity
of transforming one formalism to another.

Among all questions that we have left unsettled in this paper, we wish to list
three interesting and important questions concerning the no endmarker theorem.

  1. 1.

It is desirable to determine the “exact” stack-state complexity of
transforming endmarker 1ppda’s to error-equivalent no-endmarker 1ppda’s. If we
weaken the requirement of “error-equivalence” by allowing small additional
errors in the process of transformations, can we significantly reduce the
stack-state complexity of transformation?

  2. 2.

We may ask whether there exist much more concise 1ppda’s with no endmarker
than what we have constructed in Section 5. More specifically, for example, is
there any no-endmarker 1ppda that has only $(enm)^{O(1)}$ states and stack
alphabet size $2^{(enm)^{O(1)}}$?

  3. 3.

As we have noted in Section 1.2, since the deterministic and the
nondeterministic models of pushdown automata can be viewed as special cases of
the probabilistic model, Lemma 5.5 provides an upper bound of the stack-state
complexity of transformation for the deterministic and nondeterministic
models. However, it seems likely that a much better upper bound can be
achieved on the stack-state complexity of transformation.

## References

  * [1] J. Eremondi, O. H. Ibarra, and I. McQuillan. Insertion operations on deterministic reversal-bounded counter machines. Journal of Computer and System Sciences 104 (2019) 244–257.
  * [2] S. Ginsburg and S. Greibach. Determinsitic context free languages. Information and Control 9 (1966) 620–640.
  * [3] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
  * [4] J. Hromkovič and G. Schnitger. On probabilistic pushdown automata. Information and Computation 208 (2010) 982–995.
  * [5] O. H. Ibarra and I. McQuillan. The effect of end-markers on counter machines and commutativity. Theoretical Computer Science 627 (2016) 71–81.
  * [6] J. Kaņeps, D. Geidmanis, and R. Freivalds. Tally languages accepted by Monte Carlo pushdown automata. In the Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM’97), Lecture Notes in Computer Science, vol. 1269, pp. 187–195, 1997.
  * [7] H. R. Lewis and C. H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1st edition (1981).
  * [8] I. I. Macarie and M. Ogihara. Properties of probabilistic pushdown automata. Theoretical Computer Science 207 (1998) 117–130.
  * [9] M. Nasu and N. Honda. Fuzzy events realized by finite probabilistic automata. Information and Control 12 (1968) 284–303.
  * [10] K. Reinhardt. Counting and empty alternating pushdown automata. In J. Dassow, editor, Developments in Theoretical Computer Science: 7th IMYSC, number 6 in Topics in Computer Mathematics, Gordon and Breach Science Publishes S.A., pp.123–132, 1992.
  * [11] G. Pighizzini and A. Pisoni. Limited automata and context-free languages. Fundamenta Informaticae 136 (2015) 157–176.
  * [12] T. Yamakami. Swapping lemmas for regular and context-free languages. Manuscript, arXiv:0808.4122, 2008.
  * [13] T. Yamakami. Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages. In the Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science, vol. 8327, pp. 514–525, 2014. A complete version at arXiv:1303.1717.
  * [14] T. Yamakami. Pseudorandom generators against advised context-free languages. Theoretical Computer Science 613 (2016) 1–27.
  * [15] T. Yamakami. One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report). In the Proceedings of the 21st International Conference on Developments in Language Theory (DLT 2017), Lecture Notes in Computer Science, Springer, vol. 10396, pp. 353–364, 2017.
  * [16] T. Yamakami. Behavioral strengths and weaknesses of various models of limited automata. In the Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2019), Lecture Notes in Computer Science, Springer, vol. 11376, pp. 519–530, 2019. A complete and corrected version is available at arXiv:2111.05000, 2021.