Behavioral Strengths and Weaknesses of Various Models of Limited
Automata111This current paper completes and corrects its preliminary version,
which appeared in the Proceedings of the 45th International Conference on
Current Trends in Theory and Practice of Computer Science (SOFSEM 2019), Nový
Smokovec, Slovakia, January 27–30, 2019, Lecture Notes in Computer Science,
Springer, vol. 11376, pp. 519–530, 2019.

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

###### Abstract

We examine the behaviors of various models of $k$-limited automata, which
naturally extend Hibbard’s [Inf. Control, vol. 11, pp. 196–238, 1967] scan
limited automata, each of which is a single-tape linear-bounded automaton
satisfying the $k$-limitedness requirement that the content of each tape cell
should be modified only during the first $k$ visits of a tape head. One
central computation model is a probabilistic $k$-limited automaton
(abbreviated as a $k$-lpa), which accepts an input exactly when its accepting
states are reachable from its initial state with probability more than 1/2
within expected polynomial time. We also study the behaviors of one-sided-
error and bounded-error variants of such $k$-lpa’s as well as the
deterministic, nondeterministic, and unambiguous models of $k$-limited
automata, which can be viewed as natural restrictions of $k$-lpa’s. We discuss
fundamental properties of these machine models and obtain inclusions and
separations among language families induced by them. In due course, we study
special features—the blank skipping property and the closure under
reversal—which are keys to the robustness of $k$-lpa’s.

Keywords. limited automata, pushdown automata, probabilistic computation,
bounded-error probability, one-sided error, blank skipping property, reversal

##  1 Historical Background, Motivations, and Chellenges

###  1.1 Limited Automata

Over the past 6 decades, automata theory has made a remarkable progress to
unearth hidden structures and properties of various types of finite-state-
controlled machines, including fundamental computation models of
finite(-state) automata and one-way pushdown automata.

In an early period of the development of automata theory, Hibbard [6]
introduced a then-novel rewriting system of so-called _scan limited automata_
in hope of characterizing context-free and deterministic context-free
languages by direct simulations of their underlying one-way pushdown automata.
Unfortunately, Hibbard’s model seems to have been paid little attention until
Pighizzini and Pisoni [16, 17] reformulated the model from a modern-machinery
perspective and reproved a characterization theorem of Hibbard in a more
sophisticated manner. A _$k$ -limited automaton_,333Hibbard’s original
formulation of “$k$-limited automaton” is equipped with a semi-infinite tape
that stretches only to the right with no endmarker but is filled with the
blank symbols outside of an input string. Our definition in this paper is
different from Hibbard’s but it is rather similar to Pighizzini and Pisoni’s
[16, 17]. for each fixed index $k\geq 0$, is roughly a one-tape (or a single-
tape) Turing machine444A single-tape Turing machine model was discussed in the
past literature, including [5, 21]. whose tape head is allowed to rewrite each
tape cell between two endmarkers only during the first $k$ scans or visits
(except that, whenever a tape head makes a “turn,” we count this move as
“double” visits). after the $k$ visits to a tape cell, the last symbol in the
tape cell becomes unrewritable and frozen forever. Although these automata can
be viewed as a special case of linear-bounded finite automata, the restriction
on the number of times that they rewrite tape symbols brings in quite
distinctive effects on the computational power of the underlying automata,
different from other restrictions, such as upper bounds on the numbers of
nondeterministic choices or the number of tape-head turns. Hibbard conducted
an intensive study on deterministic and nondeterministic behaviors of
$k$-limited automata. In his study, he discovered that _nondeterministic
$k$-limited automata_ (abbreviated as $k$-lna’s) for $k\geq 2$ are exactly as
powerful as 1npda’s, whereas 1-lna’s are equivalent in power to 2-way
deterministic finite automata (or 2dfa’s) [22]. This gives natural
characterizations of 1npda’s and 2dfa’s in terms of access-controlled Turing
machines.

Another close relationship was proven by Pighizzini and Pisoni [17] between
_deterministic $k$-limited automata_ (or $k$-lda’s) and one-way deterministic
pushdown automata (or 1dpda’s). In fact, they proved that $2$-lda’s embody
exactly the power of 1dpda’s. This equivalence in computational complexity
contrasts Hibbard’s observation that, for each index $k\geq 2$, $(k+1)$-lda’s
in general possess more recognition power than $k$-lda’s. These phenomena
exhibit a clear structural difference between determinism and nondeterminism
on the machine model of “limited automata” and such a difference naturally
raises an important question of whether other variants of limited automata can
match their corresponding models of one-way pushdown automata in computational
power.

###  1.2 Extension to Probabilistic and Unambiguous Computations

Lately, a computation model of _one-way probabilistic pushdown automata_ (or
1ppda’s) has been discussed extensively to demonstrate computational strengths
as well as weaknesses in [8, 10, 15, 29].

While nondeterministic computation is purely a theoretical notion,
probabilistic computation could be implemented in real life by installing a
mechanism of generating (or sampling) random bits (e.g., by flipping fair or
biased coins). From a generic viewpoint, deterministic and nondeterministic
computations can be seen merely as restricted variants of probabilistic
computation by appropriately defining the criteria for “error probability” of
computation. A _bounded-error_ probabilistic machine makes error probability
bounded away from $1/2$, whereas an _unbounded-error_ probabilistic machine
allows error to take arbitrarily close to probability $1/2$.

In many cases, a probabilistic approach helps us solve a target mathematical
problem algorithmically faster, and probabilistic (or randomized) computation
often exhibits its superiority over its deterministic counterpart even on
simple machine models. For example, as Freivalds [2] demonstrated, 2-way
probabilistic finite automata (or 2pfa’s) running in expected exponential time
can recognize non-regular languages with bounded-error probability [2]. By
contrast, when restricted to expected subexponential runtime, bounded-error
2pfa’s recognize only regular languages [1, 9]. As this example shows, the
expected runtime bounds of probabilistic machines largely affect the
computational power of the machines, and thus its probabilistic behaviors
significantly differ from deterministic behaviors. In many studies, the
runtime of machines is limited to expected polynomial time. Probabilistic
variants of pushdown automata were discussed intensively by Hromkovič and
Schnitger [8] as well as Yamakami [29]. They demonstrated clear differences in
computational power between two pushdown models, 1npda’s and 1ppda’s.

The aforementioned usefulness of probabilistic algorithms motivates us to take
a probabilistic approach toward Hibbard’s original model of $k$-limited
automata. When $k$-limited automata are allowed to err, these machines are
naturally expected to exhibit significantly better performance in computation.
This paper in fact aims at introducing a novel model of _probabilistic
$k$-limited automata_ (or $k$-lpa’s) and their natural variants, including
one-sided-error, bounded-error, and unbounded-error models restricted to
expected polynomial running time, and to explore their fundamental properties
to obtain strengths and weaknesses of families of languages recognized by
those machine models. Since $k$-lda’s and $k$-lna’s are viewed as special
cases of $k$-lpa’s, many properties of $k$-lda’s and $k$-lna’s can be
discussed within a wider framework of $k$-lpa’s.

_Unambiguity_ has been paid special attention in formal languages and automata
theory. The unambiguity for finite automata infers a unique accepting
computation path if any. Stearns and Hunt III [20], for instance, demonstrated
that, for converting a nondeterministic finite automaton into an equivalent
finite machine, an unambiguous finite automaton performs no better than any
deterministic finite automaton. For unambiguous context-free languages, there
are known efficient algorithms to parse given words of the languages. Herzog
[4] further generalized this notion for pushdown automata and discussed the
amount of ambiguity. With the use of polynomial-size Karp-Lipton advice, as
Reinhardt and Allender [19] demonstrated, for logarithmic-space auxiliary
pushdown automata, it is possible to make nondeterministic computation
unambiguous. In this paper, we also discuss _unambiguous $k$-limited automata_
(abbreviated as $k$-lua) as an unambiguous model of $k$-lna’s. We wish to ask
what relationships are met between pushdown automata and $2$-limited automata
of the same machine types.

Let us introduce the notation for language families induced by the
aforementioned models of $k$-limited automata. The notation
$k\mbox{-}\mathrm{LPA}$ denotes the family of all languages recognized by
expected-polynomial-time $k$-lpa’s with unbounded-error probability. In a way
similar to $k\mbox{-}\mathrm{LPA}$, one-sided-error and bounded-error models
of $k$-lpa’s induce $k\mbox{-}\mathrm{LRA}$ and $k\mbox{-}\mathrm{LBPA}$,
respectively. Furthermore, $k\mbox{-}\mathrm{LDA}$, $k\mbox{-}\mathrm{LNA}$,
and $k\mbox{-}\mathrm{LUA}$ are obtained from $k\mbox{-}\mathrm{LPA}$
respectively by replacing $k$-lpa’s with $k$-lda’s, $k$-lna’s, and $k$-lua’s.
Containment relations among those language families are summarized in Fig. 1.

Figure 1: Containment relations among language families discussed in this
paper. Each upper family contains its lower family except for
$\omega\mbox{-}\mathrm{LDA}\subseteq\omega\mbox{-}\mathrm{LRA}$.

#### Organization of This Work

In Section 3.1, we will give a formal definition of $k$-lpa’s, following the
existing models of 1ppda’s explained in detail through Section 2.2. Section
2.3 argues how to convert any 1ppda to its pop-controlled form, called “ideal-
shape”. We will present a basic property of “blank skipping” of $k$-lpa’s,
which is useful together with “ideal shape” in proving Theorem 3.5 in Section
3.3. The collapses of language families induced by $k$-lpa’s and by $k$-lua’s
as in Theorem 3.11 will be proven in Section 3.5. We will discuss closure/non-
closure properties of $k$-lda’s in Section 4.1 and $k$-lpa’s in Section 4.2.
Numerous problems left unanswered throughout this paper will be listed in
Section 5 as a guiding compass to the future study of $k$-limited automata.

##  2 Fundamental Notions and Notation

Let us formally introduce various computational models of limited automata, in
which we can rewrite the content of each tape cell only during the first $k$
scans or visits of the cell. In comparison, we also describe probabilistic
pushdown automata.

###  2.1 Numbers, Alphabets, and Languages

Let $\mathbb{N}$ denote the set of all _natural numbers_ , which are
nonnegative integers, and set $\mathbb{N}^{+}$ to be $\mathbb{N}-\\{0\\}$. We
denote by $[m,n]_{\mathbb{Z}}$ the set $\\{m,m+1,m+2,\ldots,n\\}$ for any two
integers $m$ and $n$ with $m\leq n$. This set $[m,n]_{\mathbb{Z}}$ is
conveniently called an _integer interval_ in comparison to a real interval. In
addition, we abbreviate as $[m]$ the integer interval $[1,m]_{\mathbb{Z}}$ for
any integer $m\geq 1$.

A nonempty finite set of “symbols” or “letters” is called an _alphabet_. A
_string_ $x$ over alphabet $\Sigma$ is a finite sequence of symbols taken from
$\Sigma$ and its _length_ $|x|$ expresses the total number of symbols in $x$.
The _empty string_ is a unique string of length $0$ and is always denoted
$\lambda$. The notation $\Sigma^{*}$ denotes the set of all strings over
$\Sigma$ and any subset of $\Sigma^{*}$ is called a _language_ over $\Sigma$.
Given a number $n\in\mathbb{N}$, $\Sigma^{n}$ (resp., $\Sigma^{\leq n}$)
expresses the set of all strings of length exactly $n$ (resp., at most $n$)
over $\Sigma$. Obviously, $\Sigma^{*}$ coincides with
$\bigcup_{n\in\mathbb{N}}\Sigma^{n}$.

Given two alphabets $\Sigma_{1}$ and $\Sigma_{2}$, we construct a new alphabet
$\\{[\>\begin{subarray}{c}\sigma\\\
\tau\end{subarray}]\mid\sigma\in\Sigma_{1},\tau\in\Sigma_{2}\\}$ using the
_track notation_ of [21]. A string over this alphabet is of the form
$[\>\begin{subarray}{c}\sigma_{1}\\\
\tau_{1}\end{subarray}][\>\begin{subarray}{c}\sigma_{2}\\\
\tau_{2}\end{subarray}]\cdots[\>\begin{subarray}{c}\sigma_{n}\\\
\tau_{n}\end{subarray}]$, which is further abbreviated as
$[\>\begin{subarray}{c}x\\\ z\end{subarray}]$ for
$x=\sigma_{1}\sigma_{2}\cdots\sigma_{n}$ and
$z=\tau_{1}\tau_{2}\cdots\tau_{n}$. To provide such a string
$[\>\begin{subarray}{c}x\\\ z\end{subarray}]$ to an input tape, we split the
tape into two tracks so that the upper track holds $x$ and the lower track
does $z$.

Given a string $x$ of the form
$\sigma_{1}\sigma_{2}\cdots\sigma_{n-1}\sigma_{n}$ over alphabet $\Sigma$ with
$\sigma_{i}\in\Sigma$ for all $i\in[n]$, the _reverse_ of $x$ is
$\sigma_{n}\sigma_{n-1}\cdots\sigma_{2}\sigma_{1}$ and denoted by $x^{R}$.
Given a language $A$, the notation $A^{R}$ denotes the _reverse language_
$\\{x^{R}\mid x\in A\\}$. For a family ${\cal F}$ of languages, ${\cal F}^{R}$
expresses the collection of $A^{R}$ for any language $A$ in ${\cal F}$.

For any two languages $L_{1}$ and $L_{2}$, the _concatenation_ $L_{1}\cdot
L_{2}$ (more succinctly, $L_{1}L_{2}$) denotes $\\{xy\mid x\in L_{1},y\in
L_{2}\\}$. In particular, when $L_{1}$ is a singleton $\\{a\\}$, we write
$aL_{2}$ instead of $\\{a\\}\cdot L_{2}$. Similarly, when $L_{2}=\\{a\\}$, we
use the succinct notation $L_{1}a$.

Any function $h:\Sigma_{1}\to\Sigma_{2}^{*}$ for two alphabets $\Sigma_{1}$
and $\Sigma_{2}$ is called a _homomorphism_. Such a homomorphism $h$ is called
_$\lambda$ -free_ if $h(\sigma)\neq\lambda$ holds for any
$\sigma\in\Sigma_{1}$. We naturally expand a homomorphism $h$ to a map from
$\Sigma_{1}^{*}$ to $\Sigma_{2}^{*}$ by setting
$h(\sigma_{1}\sigma_{2}\cdots\sigma_{n})=h(\sigma_{1})h(\sigma_{2})\cdots
h(\sigma_{n})$ for any $\sigma_{1},\sigma_{2},\ldots,\sigma_{n}\in\Sigma_{1}$.

###  2.2 One-Way Probabilistic Pushdown Automata and Their Variants

As a fundamental computation model, we begin with _one-way probabilistic
pushdown automata_ (or 1pda’s, for short) as a basis to introduce a new model
of probabilistic $k$-limited automata in Section 3.1. _One-way deterministic
and nondeterministic pushdown automata_ (abbreviated as 1dpda’s and 1npda’s,
respectively) can be viewed as special cases of the following _one-way
probabilistic pushdown automata_ (or _1ppda’s_ , for short). We also obtain
_one-way unambiguous pushdown automata_ (or 1upda’s) as a restriction of
1npda’s.

An input string is initially placed on an input tape, surrounded by two
endmarkers ${|}\\!\\!\mathrm{c}$ (left endmarker) and $\$$ (right endmarker).
For various models of pushdown automata, the use of such endmarkers is
nonessential (see, e.g., [31]). To clarify the use of the endmarkers, however,
we explicitly include them in the description of a 1ppda.

Formally, a 1ppda $M$ is a tuple
$(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},\bot,Q_{acc},Q_{rej})$,
in which $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$ is a _probabilistic
transition function_ from
$(Q-Q_{halt})\times\check{\Sigma}_{\lambda}\times\Gamma\times
Q\times\Theta_{\Gamma}$ to $[0,1]$, $q_{0}$ ($\in Q$) is an initial state,
$\bot$ ($\in\Gamma$) is a bottom marker, $Q_{acc}$ ($\subseteq Q$) is a set of
accepting states, and $Q_{rej}$ ($\subseteq Q$) is a set of rejecting states,
$\check{\Sigma}=\Sigma\cup\\{{|}\\!\\!\mathrm{c},\$\\}$,
$\check{\Sigma}_{\lambda}=\check{\Sigma}\cup\\{\lambda\\}$, and
$Q_{halt}=Q_{acc}\cup Q_{rej}$. Let $\Gamma^{(-)}=\Gamma-\\{\bot\\}$. For a
given set $\Gamma$ of symbols, a _$\Gamma$ -symbol_ refers to any symbol in
$\Gamma$. The _push size_ of a 1ppda is the maximum length $e$ of any string
pushed into a stack by any single move, and thus
$\Theta_{\Gamma}\subseteq\Gamma^{\leq e}$ follows.

For clarity reason, we express $\delta(q,\sigma,a,p,u)$ as
$\delta(q,\sigma,a\\!\mid\\!p,u)$ with the use of a special separator “$|$”.
This value $\delta(q,\sigma,a\\!\mid\\!p,u)$ expresses the probability that,
when $M$ scans $\sigma$ on the input tape in inner state $q$, $M$ changes $q$
to $p$ and updates a topmost stack symbol $a$ to $u$. In particular, when we
always demand $\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)$, we obtain a
_one-way deterministic pushdown automaton_ (or a 1dpda). In contrast, when
$\delta(q,\sigma,a\\!\mid\\!p,u)$ is required to be either the fixed constant
or $0$, we obtain a _one-way nondeterministic pushdown automaton_ (or a
1npda).

For any
$(q,\sigma,a)\in(Q-Q_{halt})\times\check{\Sigma}_{\lambda}\times\Gamma$, we
set $\delta[q,\sigma,a]=\sum_{(p,u)\in
Q\times\Theta_{\Gamma}}\delta(q,\sigma,a\\!\mid\\!p,u)$. In the case of
$\sigma=\lambda$, we specifically call its transition a _$\lambda$ -move_ (or
a _$\lambda$ -transition_) and the tape head must stay still.

At any point, $M$ can probabilistically select either a $\lambda$-move or a
non-$\lambda$-move. This is formally stated as
$\delta[q,\sigma,a]+\delta[q,\lambda,a]=1$ for any given triplet
$(q,\sigma,a)\in(Q-Q_{halt})\times\check{\Sigma}\times\Gamma$.

Whenever $M$ reads a nonempty input symbol, the tape head of $M$ must move to
the right. During $\lambda$-moves, nevertheless, the tape head must stay
still. After reading $\$$, the tape head is considered to move off the _input
region_ , which is marked as ${|}\\!\\!\mathrm{c}{x}\$$ for input
$x\in\Sigma^{*}$. All cells on the input tape are indexed by natural numbers
from left to right, where cell $0$ is the start cell containing
${|}\\!\\!\mathrm{c}$ and cell $|x|+1$ contains $\$$ for each input $x$.

Throughout this paper, we express a _stack content_ , which is a string stored
inside the stack in a sequential order from the topmost symbol $w_{n}$ to the
bottom symbol $w_{0}=\bot$, as $w_{n}\cdots w_{2}w_{1}w_{0}$.

A _(surface) configuration_ of $M$ on input $x$ is a triplet $(q,i,w)$, which
indicates that $M$ is in inner state $q$, its tape head scans the $i$th cell,
and its stack contains $w$. The _initial configuration_ is $(q_{0},0,\bot)$.
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. We say that a configuration
$(p,j,uw)$ _follows_ $(q,i,au)$ with probability
$\delta(q,\sigma,a\\!\mid\\!p,u)$ if $\sigma$ is the $i$th input symbol and
$j=i$ if $\sigma=\lambda$ and $j=i+1$ if $\sigma\neq\lambda$. A _computation
path_ of length $k$ on the input $x$ is a series of $k$ configurations, which
describes a history of consecutive transitions (or moves) made by $M$ on $x$,
starting at the initial configuration with probability $p_{1}=1$ and the
$i+1$st configuration follows the $i$th configuration with probability $p_{i}$
and ending at a halting configuration with probability $p_{k}$. The
probability of each computation path is determined by the multiplication of
all chosen transition probabilities along the computation path. We thus assign
the probability $\Pi_{i\in[k]}p_{i}$ to such a computation path. It is
important to note that, after reading $\$$, $M$ is allowed to make a finite
series of $\lambda$-moves until it enters halting states. A computation path
is called _accepting_ (resp., _rejecting_) if the path ends with an accepting
configuration (resp., a rejecting configuration).

Generally, a 1ppda may produce an extremely long computation path or even an
infinite computation path. Following an early discussion in Section 1.1 on the
expected runtime of probabilistic machines, it is desirable to restrict our
attention to 1ppda’s whose _computation paths have a polynomial length on
average_ ; that is, there is a polynomial $p$ for which the expected length of
all terminating computation paths on input $x$ is bounded from above by
$p(|x|)$. A standard definition of 1dpda’s and 1npda’s does not have such a
runtime bound, because we can easily convert those machines to ones that halt
within $O(n)$ time (e.g., [7]). Throughout this paper, we implicitly assume
that all 1ppda’s should satisfy this expected polynomial termination
requirement. This makes it possible for us to mostly concentrate on
polynomial-length computation paths.

Given an arbitrary string $x\in\Sigma^{*}$, the _acceptance probability_ of
$M$ on $x$ is the sum of all probabilities of accepting computation paths of
$M$ starting with ${|}\\!\\!\mathrm{c}{x}\$$ written on the input tape and we
notationally 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$. We say that $M$ _accepts (resp., rejects) $x$ with probability
$p$_ if the value $p$ matches $p_{M,acc}(x)$ (resp., $p_{M,rej}(x)$). If $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 say that $M$ _accepts_ $x$ if
$p_{M,acc}(x)>1/2$ and _rejects_ $x$ if $p_{M,rej}(x)\geq 1/2$. Given a
language $L$, in general, we say that $M$ _recognizes_ $L$ if, for any $x\in
L$, $M$ accepts $x$ and, for any $x\in\Sigma^{*}-L$, $M$ rejects. 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\\}$. The _error probability of
$M$ on $x$ for $L$_ refers to the probability that $M$’s outcome is different
from $L$. We further say that $M$ makes _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$. With or without this condition, $M$ is said to make _unbounded
error_. Moreover, we say that $M$ makes _one-sided error_ if, for all strings
$x$, either $p{M,acc}(x)>\frac{1}{2}$ or $p_{M,rej}(x)=1$ holds.

We require every 1ppda to run _in expected polynomial time_. Two 1ppda’s
$M_{1}$ and $M_{2}$ are _(recognition) equivalent_ if $L(M_{1})=L(M_{2})$.
More strongly, we say that two 1ppda’s are _error-equivalent_ if they are
recognition equivalent and their error probabilities coincide with each other
on all inputs.

For any error bound $\varepsilon\in[0,1/2)$, the notations
$1\mathrm{PPDA}_{\varepsilon}$ and $2\mathrm{PFA}_{\varepsilon}$ refer to the
families of all languages recognized by (expected-polynomial-time)
$\varepsilon$-error 1ppda’s and (expected-polynomial-time) $\varepsilon$-error
2pfa’s, respectively. As a restriction of $2\mathrm{PFA}_{\varepsilon}$,
$2\mathrm{RFA}_{\varepsilon}$ denotes the family of all languages recognized
by 2pfa’s with one-sided error probability at most $\varepsilon$. Similarly,
we define $1\mathrm{RPDA}_{\varepsilon}$ as the one-sided-error variant of
$1\mathrm{PPDA}_{\varepsilon}$. In addition, we often use more familiar
notation of $\mathrm{PCFL}$, $\mathrm{BPCFL}$, and $\mathrm{RCFL}$
respectively for $1\mathrm{PPDA}_{ub}$,
$\bigcup_{0\leq\varepsilon<1/2}1\mathrm{PPDA}_{\varepsilon}$, and
$\bigcup_{0\leq\varepsilon<1}1\mathrm{RPDA}_{\varepsilon}$. The strengths and
weaknesses of $\mathrm{PCFL}$ were discussed earlier by Macarie and Ogihara
[15] and those of $\mathrm{BPCFL}$ were studied by Hromkovič and Schnitger [8]
and Yamakami [29].

In comparison, $\mathrm{REG}$ denotes the family of all _regular languages_ ,
which are recognized by one-way deterministic finite automata. Similarly,
$\mathrm{CFL}$ and $\mathrm{DCFL}$ denote the families of all languages
recognized by 1npda’s and by 1dpda’s, respectively. It follows that
$\mathrm{DCFL}=1\mathrm{PPDA}_{0}$. Notice that
$\mathrm{DCFL}\subseteq\mathrm{RCFL}\subseteq\mathrm{BPCFL}\subseteq\mathrm{PCFL}$.
Since the language $\\{a^{n}b^{n}c^{n}\mid n\geq 0\\}$ is in $\mathrm{BPCFL}$
[8], $\mathrm{BPCFL}\nsubseteq\mathrm{CFL}$ follows, further leading to
$\mathrm{PCFL}\neq\mathrm{CFL}$. Furthermore, _unambiguous computation_ refers
to nondeterministic computation consisting of at most one accepting
computation path. Let us define $\mathrm{UCFL}$ by restricting 1npda’s used
for $\mathrm{CFL}$ to produce only unambiguous computation (see, e.g., [26]).

To describe the behaviors of a stack, we use the basic terminology used in
[24, 27, 28]. A _stack content_ formally means a series $z=z_{m}z_{m-1}\cdots
z_{1}z_{0}$ of stack symbols in $\Gamma$, which are stored in the stack
sequentially from $z_{m}$ at the top of the stack to $z_{0}$ ($=\bot$) at the
bottom of the stack. We refer to a stack content obtained just after the tape
head scans and moves off the $i$th tape cell as a _stack content at the $i$th
position_. A _stack transition_ means the change of a stack content by an
application of a single move.

For two language families ${\cal F}$ and ${\cal G}$, the notation ${\cal
F}\vee{\cal G}$ (resp., ${\cal F}\wedge{\cal G}$) denotes the _2-disjunctive
closure_ $\\{A\cup B\mid A\in{\cal F},B\in{\cal G}\\}$ (resp., the
_2-conjunctive closure_ $\\{A\cap B\mid A\in{\cal F},B\in{\cal G}\\}$). For
any index $d\in\mathbb{N}^{+}$, define ${\cal F}(1)={\cal F}$ and ${\cal
F}(d+1)={\cal F}\wedge{\cal F}(d)$. Notice that
$\mathrm{DCFL}(k)\neq\mathrm{DCFL}(k+1)$ for any $k\in\mathbb{N}^{+}$ [14]
(reproven in [30] by a different argument).

###  2.3 Ideal Shape Lemma for Pushdown Automata

We start with restricting the behaviors of 1ppda’s without compromising their
language recognition power. Any 1ppda that makes such a restricted behavior is
called “ideal shape” in [31].

We want to show how to convert any 1ppda to a “push-pop-controlled” form, in
which (i) the pop operations always take place by first reading an input
symbol $\sigma$ and then making a series (one or more) of the pop operations
without reading any further input symbol and (ii) push operations add single
symbols without altering any existing stack content. In other words, a 1ppda
_in an ideal shape_ is restricted to take only the following actions. (1)
Scanning $\sigma\in\Sigma$, preserve the topmost stack symbol (called a
_stationary operation_). (2) Scanning $\sigma\in\Sigma$, push a new symbol $u$
($\in\Gamma^{(-)}$) without changing any symbol stored in the stack. (3)
Scanning $\sigma\in\Sigma$, pop the topmost stack symbol. (4) Without scanning
an input symbol (i.e., $\lambda$-move), pop the topmost stack symbol. (5) The
stack operation (4) comes only after either (3) or (4). These five conditions
can be stated more formally. We say that a 1ppda $N$ is _in an ideal shape_ if
it satisfies the following conditions. If $\delta(q,\sigma,a\\!\mid\\!p,u)\neq
0$, then (i) $\sigma=\lambda$ implies $u=\lambda$ and (ii) $\sigma\neq\lambda$
implies $u\in\\{\lambda,ba,a\\}$ for a certain $b\in\Gamma^{(-)}$. Moreover,
for any $(q,\sigma,a)$ with $\sigma\neq\lambda$, (iii) if
$\delta(q,\sigma,a\\!\mid\\!p,ba)\neq 0$ with $b\in\Gamma$, then
$\delta[p,\lambda,b]=0$ and (iv) if $\delta(q,\sigma,a\\!\mid\\!p,a)\neq 0$,
then $\delta[p,\lambda,a]=0$.

Lemma 2.1 states that any 1ppda can be converted into its “equivalent” 1ppda
in an ideal shape. The lemma was first stated in [31] for 1ppda’s equipped
with the endmarkers as well as the model of 1ppda’s without endmarkers. Note
that _1ppda with no endmarker_ is obtained from the definition of 1ppda given
in Section 2.2 simply by removing ${|}\\!\\!\mathrm{c}$ and $\$$. The
acceptance and rejection of such a no-endmarker 1ppda is determined by whether
the 1ppda is in accepting states or non-accepting states just after reading
off the entire input string.

###### Lemma 2.1

[Ideal Shape Lemma, [31]] Let $n\in\mathbb{N}^{+}$. Any $n$-state 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 the model with no endmarker.

Since error probability can differ according to inputs, by setting it
appropriately, we can obtain the ideal shape lemma for 1dpda’s and 1npda’s.
The proof of Lemma 2.1 given in [31, Section 4.2] is lengthy, consisting of a
series of transformations of automata, and is proven by utilizing, in part,
basic ideas of Hopcroft and Ullman [7, Chapter 10] and of Pighizzini and
Pisoni [17, Section 5]. For completeness of the paper, we describe a rough
sketch of the proof given in [31, Section 4.2].

Proof Sketch of Lemma 2.1.  Let us begin the proof sketch by fixing a 1ppda
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\Theta_{\Gamma},\delta,q_{0},\bot,Q_{acc},Q_{rej})$
arbitrarily. Let $|Q|=n$, $|\Gamma|=m$, and $e$ be the push size of $M$.
Starting with this machine $M$, we will perform a series of conversions of the
machine to satisfy the desired condition of the ideal shape 1ppda. To make our
description simpler, we introduce the succinct notation
$\delta^{*}[p,\lambda,a\\!\mid\\!q,\lambda,w]$ ($a\in\Gamma$ and
$w\in\Gamma^{*}$) to denote the probability of the event that, starting with
state $q$ and 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 enters state $p$ with stack content $wz$.

(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 the transitions of the form
$\delta(q,\lambda,Z_{0}|p,Z_{0})$, which violates the requirement of $M_{1}$
concerning pop operations. Notice that, once $M$ reads $\$$, it makes only
$\lambda$-moves only with states in $Q^{(\$)}$ and eventually empties the
stack.

(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 require that all $\lambda$-moves of $M_{2}$ are
limited only to either ($b$) or ($c$).

(3) We further convert $M_{2}$ to $M_{3}$ so that $M_{3}$ satisfies (2) and,
moreover, there is no operation that replaces any topmost symbol with a
different single symbol (namely, stationary operation). 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.

(4) We convert $M_{3}$ to $M_{4}$ that satisfies (3) and also makes only
$\lambda$-moves of pop operations that only follow 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.

(5) Finally, we set $M_{4}$ as the desired 1ppda $N$. $\Box$

The ideal shape lemma is useful for simplifying certain proofs associated with
1ppda’s. One such example was exhibited in [31].

###### Lemma 2.2

[31] $\mathrm{PCFL}$ is closed under reversal; that is,
$\mathrm{PCFL}^{R}=\mathrm{PCFL}$.

###  2.4 Nondeterministic Finite Automata with Output Tapes

As done in [25, 26, 27], we equip each 1nfa with a _write-once output
tape_.555An output tape is _write-once_ if its cells are initially blank, its
tape head never moves to the left, and the tape head must move to the right
whenever it writes a non-blank symbol. We use such a 1nfa as a
nondeterministic variant of Mealy machine, that is, a machine that produces a
single output symbol whenever it processes a single input symbol. Since the
machine cannot erase written output strings, we allow the machine to
_invalidate_ any produced string on the output tape by later entering a
rejecting inner state. For brevity, any 1nfa that behaves in this specific way
is called _real-time_. Let $\mathrm{rtNFAMV}$ denote the class of all multi-
valued partial functions $f$ from $\Sigma_{1}^{*}$ to $\Sigma_{2}^{*}$ whose
output values are produced on write-once tapes along only accepting
computation paths of real-time 1nfa’s ending in an accepting configuration in
which, after the real-time 1nfa’s scan the right endmarker, they enter a
designated unique accepting state, where $\Sigma_{1}$ and $\Sigma_{2}$ are
arbitrary alphabets. The last requirement on accepting configurations ensures
that the number of all distinct accepting configurations on each input $x$
equals $|f(x)|$. We further write $\mathrm{rtNFAMV}_{t}$ for the collection of
all _total_ functions in $\mathrm{rtNFAMV}$.

We define the “reversal” $f^{R}$ of a function $f$ simply by setting
$f^{R}(x)=f(x)^{R}$ for any $x\in\Sigma_{1}^{*}$. We use the notation
$\mathrm{rtNFAMV}_{t}^{R}$ for $\\{f^{R}\mid f\in\mathrm{rtNFAMV}_{t}\\}$. The
following equality holds for the functional composition “$\circ$” and this
equality will be used in Section 3.5.

###### Lemma 2.3

$\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t}=\mathrm{rtNFAMV}_{t}$.

###### Proof.

Let $h$ denote any multi-valued total function in
$\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t}$. Take two functions
$f,g\in\mathrm{rtNFAMV}_{t}$ such that $h(x)=f(g(x)^{R})$ holds for all $x$,
where $g(x)^{R}$ denotes $\\{y^{R}\mid y\in g(x)\\}$. Note that
$h(x)=\\{f(y^{R})\mid y\in g(x)\\}$. Take two real-time 1nfa’s $M_{1}$ and
$M_{2}$ with output tapes computing $f$ and $g$, respectively. For a machine
$M\in\\{M_{1},M_{2}\\}$, let
$M=(Q_{M},\Sigma,\\{cent,\$\\},\Gamma_{M},\Theta_{\Gamma_{M}},\delta_{M},q_{M,0},\bot,Q_{M,acc},Q_{M,rej})$.
Consider a machine that first runs $M_{1}$ and then runs $M_{2}^{R}$ by moving
a tape head backward. This machine correctly computes $h$ but it is not a
real-time 1nfa. Here, we want to construct another real-time 1nfa $N$ that
reads an input symbol by symbol from left to right and simulates $M_{1}$ and
$M_{2}^{R}$ simultaneously.

(i) At scanning ${|}\\!\\!\mathrm{c}$, we guess $r_{2}\in Q_{acc,M_{2}^{R}}$
and store $(q_{0,M_{1}},r_{2})$ in an internal memory. Furthermore, we guess
$r_{2}\in Q_{M_{2}^{R}}$ and $q_{2}\in Q_{M_{2}^{R}}-Q_{halt,M_{2}^{R}}$
satisfying
$(r_{1},{|}\\!\\!\mathrm{c})\in\delta_{M_{1}}(q_{0,M_{1}},{|}\\!\\!\mathrm{c})$
and
$(r_{2},{|}\\!\\!\mathrm{c})\in\delta_{M_{2}^{R}}(q_{2},{|}\\!\\!\mathrm{c})$.
Update the internal memory to $(r_{1},q_{2})$ and move to the right.

(ii) Assume that cell $\ell$ contains input symbol $\sigma\in\Sigma$ and the
internal memory of $N$ contains $(q_{1},r_{2})$. Guess $r_{1}\in Q_{M_{1}}$
and $q_{2}\in Q_{M_{2}^{R}}$ satisfying
$(r_{1},\tau)\in\delta_{M_{1}}(q_{1},\sigma)$ and
$(r_{2},\xi)\in\delta_{M_{2}^{R}}(q_{2},\tau)$. Update the memory to
$(r_{1},q_{2})$ and output $\xi$ onto $N$’s output tape.

(iii) At scanning $\$$, assume that $(q_{1},r_{2})$ is in the memory. Guess
$r_{1}\in Q_{acc,M_{1}}$ satisfying $(r_{1},\$)\in\delta_{M_{1}}(q_{1},\$)$.
We then check whether $(r_{2},\$)\in\delta_{M_{2}^{R}}(q_{0,M_{2}^{R}},\$)$.
If not, then $N$ enters a rejecting state. Otherwise, $N$ halts in accepting
states.

If there is any discrepancy in the above simulation, then our guess must be
wrong, and thus $N$ immediately enters a rejecting state.

By the above construction, the number of accepting computation paths of $N$
matches that of $M$ at any input. Therefore, we obtain
$\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t}\subseteq\mathrm{rtNFAMV}_{t}$.

Since the opposite inclusion
$\mathrm{rtNFAMV}_{t}\subseteq\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t}$
is clear, the lemma is true. ∎

##  3 Behaviors of Various Limited Automata

We will formally introduce probabilistic models of limited automata as a
foundation and explain how to obtain its variants, such as deterministic,
nondeterministic, and unambiguous models. We will then explore their
fundamental properties by making structural analyses on their behaviors.

Our first goal is to provide in the field of probabilistic computation a
complete characterization of finite and pushdown automata in terms of limited
automata. All probabilistic machines in this paper are assumed to run in
expected polynomial time.

###  3.1 Formal Definitions of Limited Automata

In a way similar to Section 2.2, we begin with an introduction of a
probabilistic model of limited automata and then define other variants by
modifying this basic model.

A _probabilistic $k$-limited automaton_ (or a _$k$ -lpa_, for short) $M$ is
formally defined as a tuple
$(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\\{\Gamma_{i}\\}_{i\in[k]},\delta,q_{0},Q_{acc},Q_{rej})$,
which accesses only tape area in between two endmarkers (those endmarkers can
be accessible but not changeable), where $Q$ is a finite set of (inner)
states, $Q_{acc}$ ($\subseteq Q$) is a set of accepting states, $Q_{rej}$
($\subseteq Q$) is a set of rejecting states, $\Sigma$ is an input alphabet,
$\\{\Gamma_{i}\\}_{i\in[k]}$ is a collection of mutually disjoint finite sets
of tape symbols, $q_{0}$ is an initial state in $Q$, and $\delta$ is a
probabilistic transition function from $(Q-Q_{halt})\times\Gamma\times
Q\times\Gamma\times D$ to the real unit interval $[0,1]$ with $D=\\{-1,+1\\}$,
$Q_{halt}=Q_{acc}\cup Q_{rej}$, and
$\Gamma=\bigcup_{i\in[0,k]_{\mathbb{Z}}}\Gamma_{i}$ for $\Gamma_{0}=\Sigma$
and ${|}\\!\\!\mathrm{c},\$\in\Gamma_{k}$. We implicitly assume that
$Q_{acc}\cap Q_{rej}=\emptyset$. The $k$-lpa has a rewritable tape, on which
an input string is initially placed, surrounded by two endmarkers
${|}\\!\\!\mathrm{c}$ and $\$$. In our formulation of $k$-lpa, unlike 1ppda’s,
the tape head always moves either to the right or to the left without stopping
still. In other words, $M$ _makes no $\lambda$-move_. We also remark that $M$
is not required to halt immediately after reading $\$$.

At any step, $M$ probabilistically chooses one of all possible transitions
given by $\delta$. For convenience, we express $\delta(q,\sigma,p,\tau,d)$ as
$\delta(q,\sigma\\!\mid\\!p,\tau,d)$, which indicates the probability that,
when $M$ scans $\sigma$ on the tape in inner state $q$, $M$ changes its inner
state to $p$, overwrites $\tau$ onto $\sigma$, and moves its tape head in
direction $d$. We set $\delta[q,\sigma]=\sum_{(p,\tau,d)\in
Q\times\Gamma\times D}\delta(q,\sigma\\!\mid\\!p,\tau,d)$. The function
$\delta$ must satisfy $\delta[q,\sigma]=1$ for every pair $(q,\sigma)\in
Q\times\Gamma$.

We say that a tape head (sometimes its underlying machine $M$) _makes a left
turn_ at cell $n$ if the tape head moves to the right into cell $n$ and then
moves back to the left at the next step. Similarly, we define a _right turn_.
For convenience, the tape head is said to _make a turn_ if it makes either a
left turn or a right turn. See Fig. 3 for a tape-head movement.

The $k$-lpa $M$ must satisfy the following _$k$ -limitedness requirement_.
During the first $k$ scans of each tape cell, at the $i$th scan with $0\leq
i<k$, if $M$ reads the content of the cell containing a symbol in
$\Gamma_{i}$, then $M$ updates the cell content to another symbol in
$\Gamma_{i+1}$. After the the $k$th scan, the cell becomes unchangeable (or
_frozen_); that is, $M$ still reads a symbol in the cell but $M$ no longer
alters the written symbol. For this rule, there is one exception: whenever the
tape head makes a turn at any tape cell, we count this move as “double scans”
or “double visits.” To make the endmarkers special, we further assume that no
symbol in $\bigcup_{i\in[0,k-1]_{\mathbb{Z}}}\Gamma_{i}$ replaces the
endmarkers. The above requirement is formally stated as follows.

> The $k$-limitedness requirement: for any transition $\delta(q,\sigma\mid
> p,\tau,d)\neq 0$ with $p,q\in Q$, $d\in\\{+1,-1\\}$, $\sigma\in\Gamma_{i}$,
> and $\tau\in\Gamma_{j}$ with $i,j\in[0,k]_{\mathbb{Z}}$, (1) if $i=k$, then
> $\sigma=\tau$ and $j=k$, (2) if $i<k$ and $i$ is even, then
> $j=i+2^{(1-d)/2}$, and (3) if $i<k$ and $i$ is odd, then $j=i+2^{(1+d)/2}$.

We assume that all tape cells are indexed by natural numbers, where the cell
containing the left endmarker is indexed $0$ (such the cell is called the
_start cell_), the cell of the right endmarker is $n+1$ if an input $x$ is of
length $n$. Most notions and notations used for 1ppda’s in Section 2.2 are
applied to $k$-lpda’s with slight modifications if necessary. A _(surface)
configuration_ of $M$ on input $x$ is a triplet of the form $(q,j,w)$, which
indicates that $M$ is in state $q$ scanning the $j$th cell of the tape
composed of ${|}\\!\\!\mathrm{c}w\$$. Similarly to the case of 1ppda’s, a
_computation path_ of $M$ on $x$ is a series of configurations generated by
applying $\delta$ repeatedly and we associate such a computation path with a
probability of generating the computation path. A _computation_ of $M$ on $x$
relates to a _computation graph_ whose vertices are distinct configurations of
$M$ on $x$ and (directed) edges represent single transitions of $M$ between
two configurations. Similarly to 1ppda’s, we also define the notions of
acceptance/rejection probability, one-sided error, bounded-error, and
unbounded-error for $k$-lpa’s as well as the notations, such as $p_{acc,M}(x)$
and $p_{rej,M}(x)$. Concerning the running time of $k$-lpa’s, similarly to
1ppda’s in Section 2.2, we implicitly assume that all $k$-lpa’s in this work
_run in expected polynomial time_.

When a string $w$ is written on a tape, the _$w$ -region_ of the tape refers
to a series of consecutive cells that hold each symbol of $w$, provided that
$w$ can be identified uniquely on the tape from the context. Even after some
symbols of $w$ is altered, we may use the same term “$w$-region” as long as
the referred cells in the original region are easily discernible from the
context. Moreover, a _blank region_ is a series of consecutive cells
containing only $B$s whose ends are both adjacent to non-blank cells. A
_fringe_ of a blank region is a non-blank cell adjacent to one of the ends of
the blank region. Since two endmarkers cannot be changed, each blank region
always has two fringes. We say that $M$ _enters the $w$-region in direction
$d$ in inner state $q$_ if, at a certain step, $M$ moves into the $d$-side of
the $w$-region from the outside of $w$ by changing its inner state to $q$,
where “$d$-side” means the left-side if $d=-1$ and the right-side if $d=+1$.
Moreover, $M$ _leaves the $w$-region in direction $d$ in inner state $q$_ if,
at a certain step, $M$ moves out of the $d$-side of the $w$-region from the
inside of $w$ by changing its inner state to $q$.

Given an index $k\geq 1$ and a constant $\varepsilon\in[0,1]$, the basic
notation $k\mbox{-}\mathrm{LPA}_{\varepsilon}$ refers to the family of all
languages recognized by (expected-polynomial-time) $k$-lpa’s with error
probability at most $\varepsilon$. In the bounded-error model, $\varepsilon$
is bounded away from $1/2$, and thus the union
$\bigcup_{\varepsilon\in[0,1/2)}k\mbox{-}\mathrm{LPA}_{\varepsilon}$ ia
abbreviated as $k\mbox{-}\mathrm{LBPA}$. In the case of the unbounded-error
model, by contrast, we write $k\mbox{-}\mathrm{LPA}$ (occasionally, we write
$k\mbox{-}\mathrm{LPA}_{ub}$ for clarity). Similarly,
$k\mbox{-}\mathrm{LRA}_{\varepsilon}$ is defined by (expected-polynomial-time)
one-sided $\varepsilon$-error $k$-lpa’s. Let
$k\mbox{-}\mathrm{LRA}=\bigcup_{\varepsilon\in[0,1)}k\mbox{-}\mathrm{LRA}_{\varepsilon}$
and
$k\mbox{-}\mathrm{LRA}_{<1/2}=\bigcup_{\varepsilon\in[0,1/2)}k\mbox{-}\mathrm{LRA}_{\varepsilon}$.

Furthermore, by requiring $k$-lna to produce only unambiguous computation on
every input, we can introduce a machine model of _unambiguous $k$-limited
automata_ (or $k$-lua’s, for short). Using $k$-lda’s, $k$-lna’s, and $k$-lua’s
as underlying machines, the notations $k\mbox{-}\mathrm{LDA}$,
$k\mbox{-}\mathrm{LNA}$, and $k\mbox{-}\mathrm{LUA}$ are used to express the
families of all languages recognized by $k$-lda’s, $k$-lna’s, and $k$-lua’s,
respectively.

Among all the aforementioned language families, it follows from the above
definitions that, for each index $k\geq 2$, $k\mbox{-}\mathrm{LDA}\subseteq
k\mbox{-}\mathrm{LUA}\subseteq k\mbox{-}\mathrm{LNA}$,
$k\mbox{-}\mathrm{LDA}\subseteq k\mbox{-}\mathrm{LRA}_{\varepsilon}\subseteq
k\mbox{-}\mathrm{LNA}$, and
$k\mbox{-}\mathrm{LRA}_{\varepsilon^{\prime}}\subseteq
k\mbox{-}\mathrm{LBPA}_{\varepsilon^{\prime}}\subseteq
k\mbox{-}\mathrm{LPA}_{\varepsilon^{\prime}}$ for any constants
$\varepsilon\in[0,1)$ and $\varepsilon^{\prime}\in[0,1/2)$. By amplifying the
success probability of $k$-lra’s, it is possible to show the further
inclusion: $k\mbox{-}\mathrm{LRA}\subseteq k\mbox{-}\mathrm{LBPA}$ for every
index $k\geq 1$. This inclusion is not obvious from the definition because a
$k$-lra can make error probability greater than $1/2$, which is not bounded-
error probability.

###### Lemma 3.1

For any $k\geq 1$, $k\mbox{-}\mathrm{LRA}\subseteq k\mbox{-}\mathrm{LBPA}$.

###### Proof.

Take any $k$-lra $M$ and assume without loss of generality that
$\varepsilon\geq 1/2$. Choose a constant $\delta$ satisfying
$0<\delta<\frac{1-\varepsilon}{2(1+\varepsilon)}$. We set
$\alpha=1-\frac{1-2\delta}{2\varepsilon}$. Given an input $x$, we first run
$M$ on $x$. Whenever $M$ enters a rejecting state, we accept with probability
$\alpha$ and reject with probability $1-\alpha$. On the contrary, when $M$
enters an accepting state, we accept with probability $1$. For any input $x\in
L(M)$, the total acceptance probability becomes
$1-\varepsilon+\varepsilon\cdot\alpha\geq\frac{1}{2}+\delta$. For the other
input $x\notin L(M)$, the total rejection probability is
$1-\alpha\geq\frac{1}{2}+\delta$. Hence, $L(M)$ belongs to
$k\mbox{-}\mathrm{LBPA}$. ∎

We further define $\omega\mbox{-}\mathrm{LPA}$ to be the union
$\bigcup_{k\in\mathbb{N}^{+}}k\mbox{-}\mathrm{LPA}$. Similarly, we can define
$\omega\mbox{-}\mathrm{LDA}$, $\omega\mbox{-}\mathrm{LRA}$,
$\omega\mbox{-}\mathrm{LBPA}$, and $\omega\mbox{-}\mathrm{LNA}$. It then
follows that
$\omega\mbox{-}\mathrm{LDA}\subseteq\omega\mbox{-}\mathrm{LRA}\subseteq\omega\mbox{-}\mathrm{LBPA}\subseteq\omega\mbox{-}\mathrm{LPA}$.

###  3.2 Blank Skipping Property for Limited Automata

Hibbard [6] proved that $\omega\mbox{-}\mathrm{LNA}=\mathrm{CFL}$ and
Pighizzini and Pisoni [17] demonstrated that $2\mbox{-}\mathrm{LDA}$ coincides
with $\mathrm{DCFL}$. It is also possible to show that $\mathrm{PCFL}\subseteq
2\mbox{-}\mathrm{LPA}$ and $\mathrm{BPCFL}\subseteq 2\mbox{-}\mathrm{LBPA}$
using the ideal-shape property of $\mathrm{PCFL}$ and $\mathrm{BPCFL}$ (see
Lemma 3.8); however, the opposite inclusions are not known to hold. Therefore,
our purpose of exact characterizations of $\mathrm{PCFL}$ and $\mathrm{BPCFL}$
requires a specific property of $k$-lpa’s, called _blank skipping_ , for which
a $k$-lpa writes only a unique blank symbol, say, $B$ during the $k$th visit
and it makes only the same deterministic moves while reading $B$ in such a way
that it neither changes its inner state nor changes the head direction (either
to the right or to the left); in other words, it behaves exactly in the same
way while reading consecutive blank symbols. When a $k$-lpa passes a cell for
the $k$th time, it must make the cell _blank_ (i.e., the cell has $B$) and the
cell becomes _frozen_ afterward. This property plays an essential role in
simulating various limited automata on pushdown automata. In what follows, we
define this property for various limited automata.

###### Definition 3.2

Let $k\in\mathbb{N}^{+}$. A $k$-limited automaton is said to be _blank
skipping_ if (1) $\Gamma_{k}=\\{{|}\\!\\!\mathrm{c},\$,B\\}$, where $B$ is a
unique blank symbol, and (2) while reading a consecutive series of
$B$-symbols, the machine must maintain the same inner states and the same head
direction in a deterministic fashion. More formally, the condition (2) states
that there are two disjoint subsets $Q_{+1},Q_{-1}$ of $Q$ for which
$\delta(q,B\mid q,B,d)=1$ for any direction $d\in\\{\pm 1\\}$ and any inner
state $q\in Q_{d}$. See Fig. 2.

To emphasize the use of the _blank skipping property_ , we append the prefix
“bs-”, as in $\mathrm{bs}\mbox{-}k\mbox{-}\mathrm{LPA}_{\varepsilon}$ and
$\mathrm{bs}\mbox{-}k\mbox{-}\mathrm{LUA}$.

Figure 2: A tape head that makes blank skipping.

Let us start to prove the blank skipping property of nondeterministic limited
automata.

###### Lemma 3.3

[Blank Skipping Lemma] Let $k$ be any integer with $k\geq 2$. Given any
$k$-lna $M$, there exists another $k$-lna $N$ such that (1) $N$ is blank-
skipping, (2) $N$ is recognition-equivalent to $M$, and (3) the number of
accepting computation paths of $N$ matches that of $M$ on every input.

In the case of $k$-lda’s, as shown in Proposition 3.4, we can transform
limited automata into their blank skipping form and this is, in fact, a main
reason that $2\mbox{-}\mathrm{LDA}$ equals $\mathrm{DCFL}$ (due to Theorem
3.5(2) with setting $\varepsilon=0$ and using
$\mathrm{DCFL}=1\mathrm{PPDA}_{0}$). From Lemma 3.3, the proposition follows
immediately because the inclusions
$\mathrm{bs}\mbox{-}k\mbox{-}\mathrm{LDA}\subseteq k\mbox{-}\mathrm{LDA}$,
$\mathrm{bs}\mbox{-}k\mbox{-}\mathrm{LNA}\subseteq k\mbox{-}\mathrm{LNA}$, and
$\mathrm{bs}\mbox{-}k\mbox{-}\mathrm{LUA}\subseteq k\mbox{-}\mathrm{LUA}$ are
obvious and Lemma 3.3 yields the opposite inclusions as well.

###### Proposition 3.4

For each index $k\geq 2$,
$k\mbox{-}\mathrm{LDA}=\mathrm{bs}\mbox{-}k\mbox{-}\mathrm{LDA}$ and
$k\mbox{-}\mathrm{LUA}=\mathrm{bs}\mbox{-}k\mbox{-}\mathrm{LUA}$.

In what follows, let us begin the proof of Lemma 3.3.

Proof of Lemma 3.3.  The following argument uses in part a basic idea of
Pighizzini and Pisoni [17]. We first describe the proof of the lemma for
$k$-lda’s and then explain how to amend it for $k$-lna’s (and thus for
$k$-lua’s).

Let $k\geq 2$ be any integer and let
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\\{\Gamma_{i}\\}_{i\in[k]},\delta,q_{0},Q_{acc},Q_{rej})$
be any $k$-lda. Let $\Gamma=\bigcup_{i\in[0,k]_{\mathbb{Z}}}\Gamma_{i}$ with
$\Gamma_{0}=\Sigma$. Note that, as long as $a\in\Gamma-\Gamma_{k}$, we can
uniquely determine the tape-head direction from $a$ alone. Let $D=\\{\pm 1\\}$
and set $\ell=|Q\times D|$.

Firstly, we modify $M$ so that $M$ remembers the tape-head direction at the
current step. This can be done by defining a new machine with the following
items. Let $\tilde{q}_{0}=(q_{0},+1)$, $\tilde{Q}=Q\times D$,
$\tilde{Q}_{acc}=\\{(q,d)\mid q\in Q_{acc},d\in D\\}$,
$\tilde{Q}_{rej}=\\{(q,d)\mid q\in Q_{rej},d\in D\\}$,
$\tilde{\delta}((q,d),a)=((p,d^{\prime}),b,d^{\prime})$ whenever
$\delta(q,a)=(p,b,d^{\prime})$. For simplicity, hereafter, we assume that $M$
has these items $\tilde{Q}$, $\tilde{Q}_{acc}$, $\tilde{Q}_{rej}$,
$\tilde{q}_{0}$, and $\tilde{\delta}$, but we intentionally drop “$\sim$”
(tilde) and write them as $Q$, $Q_{acc}$, $Q_{rej}$, $q_{0}$, and $\delta$,
respectively.

Let us introduce two notations $S_{\delta}$ and $D_{\delta}$. For each string
$w$, let $S_{\delta}(q,d\\!\mid\\!w\\!\mid\\!q^{\prime},d^{\prime})$ equal $1$
if $M$ enters the $w$-region in direction $d$ in inner state $q$, stays in the
inside of the $w$-region, and eventually leaves the $w$-region in direction
$d^{\prime}$ in inner state $q^{\prime}$, and let
$S_{\delta}(q,d\\!\mid\\!w\\!\mid\\!q^{\prime},d^{\prime})$ be $0$ otherwise.
We also set $T_{w}=(t_{ij})_{i,j\in Q\times D}$ to be an $\ell\times\ell$
$\\{0,1\\}$-matrix such that, for any index pair $i=(q,d)$ and
$j=(q^{\prime},d^{\prime})$ in $Q\times D$, the value $t_{ij}$ equals
$S_{\delta}(i\\!\mid\\!w\\!\mid\\!j)$. Since the total number of distinct
matrices $T_{w}$ for any $w$ is at most $2^{\ell}$, it is possible to use
$T_{w}$ as a part of inner states of $N$. Moreover, let
$D_{\delta}(T_{u}\\!\mid\\!q,d\\!\mid\\!T_{v})$ denote the set of all pairs
$(s,d^{\prime})$ such that, when $d=+1$ (resp., $d=-1$), $M$ enters the
$v$-region (resp., the $u$-region) in direction $-1$ (res., $+1$), stays in
the $uv$-region, and eventually leaves the $uv$-region in direction
$d^{\prime}$ in state $q^{\prime}$. To compute the value
$D_{\delta}(T_{u}\\!\mid\\!q,d\\!\mid\\!T_{v})$, we need to use two matrices
$T_{u}$ and $T_{v}$ but we do not need to remember $u$ and $v$.

In what follows, we wish to consider only the case of even $k$ because the
other case is similar in principle. We construct the desired machine
$N=(Q^{\prime},\Sigma,\\{\Gamma^{\prime}_{i}\\}_{i\in[k]},\delta^{\prime},q^{\prime}_{0},Q^{\prime}_{acc},Q^{\prime}_{rej})$
from $M$. The desired $k$-lda $N$ works as follows. Here, we try to meet the
following requirements during the construction of $N$. The new machine $N$
uses the same tape symbols as $M$ does, but $N$ also writes down other symbols
of the form $[T_{w},a,\emptyset]$, $[\emptyset,a,T_{w}]$, or $[T_{w},a,T_{u}]$
to mark a fringe of a blank region. When $N$ writes $B$ over a non-blank
symbol, it enters inner states of the form $[T_{w},s]$ or $[T_{w},s,d]$ with
$s\in Q$ and $d\in D$. While $N$ stays in a blank region, however, it keeps
the same inner states of the form $[T_{u},s,d]$. We first deal with the case
where the tape head moves from the left to the current cell.

1\. In the case of the first at most $k-2$ visits to the current cell, $N$
simulates $M$ precisely.

2\. At the $(k-1)$th visit to the current cell containing symbol
$a\notin\Gamma_{k}$, if $M$ changes the current inner state, say, $q$ to $p$
(where $p,q\in Q$) and writes $f\in\Gamma_{k}$ over the symbol $a$, then $N$
writes $B$ and changes $q$ to $[T_{f},p]$ as a new inner state of $N$.

3\. At the $(k-1)$th visit to $a\notin\Gamma_{k}$, we assume that $N$ already
has inner state $[T_{f},q]$, which indicates that $M$ has just written a
$\Gamma_{k}$-symbol $f$ in the previous step over a certain
non-$\Gamma_{k}$-symbol. Let us consider two subcases. (a) If $M$ changes $q$
to $p$ and writes $b\notin\Gamma_{k}$, then $N$ enters inner state $p$ and
writes $[T_{f},b,\emptyset]$. (b) In contrast, assume that $M$ writes
$g\in\Gamma_{k}$ instead of $b$. If $M$ moves to the right with no turn, then
$N$ writes $B$, enters inner state $[T_{fg},p]$, and moves to the right. If
$M$ makes a left turn and
$D_{\delta}(T_{f}\\!\mid\\!p,-1\\!\mid\\!T_{g})=(s,-1)$ (resp., $(s,+1)$),
then $N$ enters $[T_{fg},s,-1]$ (resp., $[T_{fg},s,+1]$), moving to the left
(resp., the right) since $(s,d)$ indicates that, once $M$ enters a region of
consecutive $\Gamma_{k}$-symbols, it will leave this region in inner state $s$
and in direction $d$.

4\. Assume that $N$ scans symbol $[\emptyset,a,T_{u}]$ in inner state $q$ at a
fringe of a certain blank region. If $M$ moves to the right, changes $q$ to
$p$, and satisfies $D_{\delta}(\emptyset\\!\mid\\!q,+1\\!\mid\\!T_{u})=(s,d)$,
then $N$ enters inner state $[T_{u},s,d]$.

5\. In a blank region, $N$ maintains the same inner state of the form
$[T_{u},s,d]$ while moving in the same direction $d\in\\{L,R\\}$.

6\. Consider the situation in which $N$ leaves the right end of a blank region
with inner state $[T_{u},s,+1]$ into its fringe that holds a symbol of the
form $[T_{v},b,\emptyset]$. There are three subcases to consider separately.
(a) If $M$ moves from this fringe to the right, changes the existing symbol,
say, $b$ to $b^{\prime}\notin\Gamma_{k}$, and enters inner state $p$, then $N$
updates the cell’s symbol $b$ to $[T_{u},b^{\prime},\emptyset]$ and enters
inner state $p$. (b) In contrast, when $M$ changes $b$ to $f\in\Gamma_{k}$
instead, then $N$ overwrites $B$ and enters inner state $[T_{uf},p]$. In this
case, the blank region grows rightwards. (c) On the contrary, when $M$ makes a
left turn, then $N$ enters inner state $[T_{uf},s^{\prime},d]$ if
$D_{\delta}(T_{u}\\!\mid\\!p,-1\\!\mid\\!T_{f})=(s^{\prime},d)$.

7\. Assume that $N$ leaves the right end of a blank region in inner state
$[T_{w},s,+1]$ to a non-blank cell holding a symbol of the form
$[T_{u},a,T_{v}]$. (a) If $M$ enters $p$ from $s$, writes
$a^{\prime}\notin\Gamma_{k}$, and moves to the right with
$D_{\delta}(\emptyset\\!\mid\\!p,-1\\!\mid\\!T_{v})=(s^{\prime},d)$, then $N$
writes $[T_{w},a^{\prime},T_{v}]$, enters inner state $[T_{v},s^{\prime},d]$,
and moves to the right. (b) In contrast, if $M$ writes $f\in\Gamma_{k}$
instead of $a^{\prime}$ with
$D_{\delta}(T_{w}\\!\mid\\!q,-1\\!\mid\\!T_{v})=(s^{\prime},d)$, then $N$
writes $B$, enters inner state $[T_{wv},s^{\prime},d]$, and moves to the
right.

8\. All other cases (such as $M$’s tape head moves in an opposite direction)
can be similarly treated.

In the case where $M$ is a $k$-lna, we wish to add an extra explanation of how
to amend the aforementioned procedure to deal with any nondeterministic
computation of $M$. Since $M$ makes nondeterministic choices at every step, we
need to apply the above procedure to each of those choices. We also need to
change the definition of $S_{\delta}$ and $D_{\delta}$ to represent
“probabilities” of the associated events to happen. Recall that
nondeterministic moves can be viewed as a special case of probabilistic moves.
As one sees, if $M$ accepts an input $x$ with error probability
$\varepsilon(x)$, then so does $N$, and vice versa. Therefore, every $k$-lna
can be simulated by the blank-skipping $k$-lna constructed above. This
completes the proof of the lemma. $\Box$

###  3.3 Applications of the Blank Skipping Property

Let us explore the usefulness of the blank skipping property of various models
of $1$-limited and $2$-limited automata. This rather fundamental property
links such limited automata to their associated pushdown automata. More
precisely, the following characterizations hold.

###### Theorem 3.5

Let $\varepsilon\in[0,1/2)$ and $\varepsilon^{\prime}\in[0,1)$ be any two
error bounds.

  1. 1.

$2\mathrm{PFA}_{\varepsilon}=1\mbox{-}\mathrm{LPA}_{\varepsilon}$,
$2\mathrm{RFA}_{\varepsilon^{\prime}}=1\mbox{-}\mathrm{LRA}_{\varepsilon^{\prime}}$,
and $2\mathrm{PFA}_{ub}=1\mbox{-}\mathrm{LPA}_{ub}$.

  2. 2.

$1\mathrm{PPDA}_{\varepsilon}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LPA}_{\varepsilon}$,
$1\mathrm{RPDA}_{\varepsilon^{\prime}}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LRA}_{\varepsilon^{\prime}}$,
and $1\mathrm{PPDA}_{ub}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LPA}_{ub}$.

  3. 3.

$\mathrm{DCFL}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LDA}$,
$\mathrm{CFL}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LNA}$, and
$\mathrm{UCFL}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LUA}$.

Although the equalities $\mathrm{DCFL}=2\mbox{-}\mathrm{LDA}$ and
$\mathrm{CFL}=2\mbox{-}\mathrm{LNA}$ are already known [6, 17], we
intensionally include them in Theorem 3.5(3) in order to clarify the
usefulness of the blank skipping lemma for them.

As an immediate consequence, $\mathrm{RCFL}$, $\mathrm{PCFL}$, and
$\mathrm{BPCFL}$ are also characterized in terms of blank-skipping limited
automata similarly to $\mathrm{DCFL}$, $\mathrm{CFL}$, and $\mathrm{UCFL}$.

###### Corollary 3.6

$\mathrm{RCFL}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LRA}$,
$\mathrm{PCFL}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LPA}$, and
$\mathrm{BPCFL}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LBPA}$.

Let us prove Theorem 3.5. Item (2) of the theorem, in particular, follows from
the fact shown in Section 2.3 that 1ppda’s can be converted into their “ideal
shapes.” The proof of the theorem relies on two supporting lemmas: Lemmas 3.7
and 3.8. Lemma 3.7 helps us convert blank-skipping 2-lpa’s into error-
equivalent 1ppda’s and Lemma 3.8 helps us convert ideal-shape 1ppda’s into
error-equivalent blank-skipping 2-lpda’s.

###### Lemma 3.7

Let $n\geq 2$. Every $n$-state blank-skipping 2-lpa working on an alphabet can
be converted into an error-equivalent 1ppda with at most $2n$ inner states.

###### Proof.

Given a blank-skipping 2-lpa $M$ over input alphabet $\Sigma$ with
$\\{\Gamma^{(1)},\Gamma^{(2)}\\}$, we wish to simulate it on an appropriate
1ppda, say, $N$ with the same error probability. Starting with input $x$, when
$M$ reads a new input symbol $\sigma\in\Sigma$ and changes it to $\tau$ in a
single step, we read $\sigma$ and push $\tau$ into a stack. We remember a
tape-head direction of $M$ internally (using inner states). In contrast, when
$M$ moves its tape head leftwards by skipping the blank symbols $B$ to the
first non-blank symbol, say, $\tau\in\Gamma^{(1)}$ and changes it to $B$, we
simply pop a topmost stack symbol.

More formally, let
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\\{\Gamma^{(1)},\Gamma^{(2)}\\},\delta,q_{0},Q_{acc},Q_{rej})$
denote any $n$-state blank-skipping 2-lpa with error probability
$\varepsilon(x)$ for every input $x$ on a fixed alphabet $\Sigma$. 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})$
in the following way. Firstly, we set $Q^{\prime}=\\{q^{(r)}\mid q\in
Q,r\in\\{+,-\\}\\}$, $Q^{\prime}_{acc}=\\{q^{(r)}\mid q\in
Q_{acc},r\in\\{+,-\\}\\}$, and $Q^{\prime}_{rej}=\\{q^{(r)}\mid q\in
Q_{rej},r\in\\{+,-\\}\\}$, where “$+$” and “$-$” respectively express the
tape-head directions “$+1$” and “$-1$” of $\delta$. We further set the initial
state $q^{\prime}_{0}$ to be $q^{(+)}_{0}$. The desired transition function
$\delta^{\prime}$ is described in the following table.

Let $a\in\Gamma^{\prime}$, $\sigma^{(1)}\in\Gamma^{(1)}$, and
$p^{(*)}\in\\{p^{(+)},p^{(-)}\\}$ for any $p\in Q$. We also write $\sigma$ in
$\Sigma$ as $\sigma^{(0)}$ for clarity.

$\delta^{\prime}(q^{(+)},\sigma^{(0)},a\\!\mid\\!p^{(+)},\sigma^{(1)}a)=\delta(q,\sigma^{(0)}\\!\mid\\!p,\sigma^{(1)},+1)$ |
---|---
$\delta^{\prime}(q^{(+)},\sigma^{(0)},a\\!\mid\\!p^{(-)},\sigma^{(1)}a)=\delta(q,\sigma^{(0)}\\!\mid\\!p,B,-1)$ |
$\delta^{\prime}(q^{(*)},\lambda,\sigma^{(1)}\\!\mid\\!p^{(+)},\lambda)=\delta(q,\sigma^{(1)}\\!\mid\\!p,B,+1)$ | $\delta^{\prime}(q^{(-)},\lambda,\sigma^{(1)}\\!\mid\\!p^{(-)},\lambda)=\delta(q,\sigma^{(1)}\\!\mid\\!p,B,-1)$
$\delta^{\prime}(q^{(+)},\lambda,a\\!\mid\\!p^{(+)},a)=\delta(q,B\\!\mid\\!p,B,+1)$ | $\delta^{\prime}(q^{(-)},\lambda,a\\!\mid\\!p^{(-)},a)=\delta(q,B\\!\mid\\!p,B,-1)$
$\delta^{\prime}(q^{(+)}_{0},{|}\\!\\!\mathrm{c},\bot\\!\mid\\!p^{(+)},\bot)=\delta(q_{0},{|}\\!\\!\mathrm{c}\\!\mid\\!p,{|}\\!\\!\mathrm{c},+1)$ | $\delta^{\prime}(q^{(+)},\$,a\\!\mid\\!p^{(-)},a)=\delta(q,\$\\!\mid\\!p,\$,-1)$

By the definition of $\delta^{\prime}$, it is obvious that the
acceptance/rejection probability of $N$ matches that of $M$. Moreover, the
state complexity of $N$ is exactly $|Q^{\prime}|=2|Q|=2n$. ∎

The ideal-shape form of 1ppda’s is a key to Lemma 3.8.

###### Lemma 3.8

Let $n,l\in\mathbb{N}^{+}$. Let $L$ be a language over alphabet $\Sigma$ of
size $l$ recognized by an $n$-state 1ppda $M$ in an ideal shape with error
probability $\varepsilon(x)$ for any input $x$. There is a blank-skipping
$2$-lpa $N$ that has $O(nl)$ states and recognizes $L$ with the same error
probability. The average runtime of $N$ is $O(|x|^{2})$ multiplied by the
average runtime of $M$ for any input $x$.

###### Proof.

Let $n$ and $l$ be any two constants in $\mathbb{N}^{+}$ and let $\Sigma$
denote any alphabet of size $l$. We take a language $L\subseteq\Sigma^{*}$ and
an ideal-shape 1ppda
$M=(Q,\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\Gamma,\delta,q_{0},\bot,Q_{acc},Q_{rej})$
that recognizes $L$ with error probability $\varepsilon(x)$ for any input $x$.

Without loss of generality, we further assume that, along each computation
path, $M$ enters a halting state only on or after reading the endmarker $\$$
followed by a (possible) series of $\lambda$-moves. We want to construct a
$2$-lpa
$N=(Q^{\prime},\Sigma,\\{\Gamma_{i}\\}_{i\in[2]},\delta^{\prime},q^{\prime}_{0},Q^{\prime}_{acc},Q^{\prime}_{rej})$
to simulate $M$ with the same error probability. A basic idea of the
simulation of $M$ proceeds in the following way. Assuming that $M$ reads a new
input symbol $\sigma$, if $M$ pushes a stack symbol $a$ into its stack, then
we change $\sigma$ into $a$. If $M$ pops a topmost stack symbol, then we move
a tape head leftwards to read the first non-blank symbol (which corresponds to
the topmost stack symbol) and then replace it with $B$ (blank symbol). In the
case where $M$ makes a $\lambda$-move, since $M$’s move must be a pop
operation because of the ideal-shape form, we take the same action as stated
before. In order to make this simulation blank-skipping, we further need to
remember a state-stack pair of $M$’s last step and utilize it to skip a blank
region.

To implement the above basic idea, we introduce the special notation of $[qa]$
to indicate that $M$ is in inner state $q$, reading stack symbol $a$ as well
as a certain nonempty input symbol. We define $Q^{\prime}$ to be
$(Q\times\Sigma)\cup Q$. A new initial state $q^{\prime}_{0}$ is set to be
$[q_{0}\bot]$ and we define $\Gamma_{0}=\Sigma$ and
$\Gamma_{2}=\\{{|}\\!\\!\mathrm{c},\$,B\\}$. For simplicity, we use the same
notation $B$ to express “blank” in $\Gamma_{1}$ as well as in $\Gamma_{2}$.
This irregular usage does not cause any problem because we can easily
transform it into a standard $2$-lpa by adding extra symbols and extra
transitions.

In contrast, while $M$ makes a series of $\lambda$-moves, $N$ stays in inner
states taken from $Q$. When $M$ pushes $b$ and enters state $p$ with
probability $\gamma$, $N$ changes its inner state $[qa]$ to $[pb]$ and writes
$a$ over $\sigma$ with the same probability. When $M$ pops and enters state
$p$ from $q$, $N$ updates $\sigma$ to $B$, changes its inner state $[qa]$ to
$p$. Recall that a pop operation at a non $\lambda$-move triggers a series of
pop operations at $\lambda$-moves. Hence, we can move the tape head to the
left and to delete the corresponding symbols. Moreover, $N$ always skips the
blank symbol $B$ with probability $1$. It is clear that
$|Q^{\prime}|=|Q||\Sigma|+|\\{\bar{q}\mid q\in Q\\}|=nl+n\leq 2nl$.

The formal definition of $\delta^{\prime}$ is given in the following table.
Let $\sigma\neq\lambda$ and $\sigma\in\Sigma$.

$\delta^{\prime}([qa],\sigma\\!\mid\\![pa],B,+1)=\delta(q,\sigma,a\\!\mid\\!p,a)$ | $\delta^{\prime}([qa],\sigma\\!\mid\\![pb],a,+1)=\delta(q,\sigma,a\\!\mid\\!p,ba)$
---|---
$\delta^{\prime}([qa],\sigma\\!\mid\\!p,B,-1)=\delta(q,\sigma,a\\!\mid\\!p,\lambda)$ ($a\neq\bot$) |  $\delta^{\prime}(q,a\\!\mid\\!p,B,-1)=\delta(q,\lambda,a\\!\mid\\!p,\lambda)$ ($a\neq\bot$)
$\delta^{\prime}(q,a\\!\mid\\![qa],B,+1)=1$ whenever $\delta[q,\lambda,a]=0$ |
$\delta^{\prime}([qa],B\\!\mid\\![qa],B,+1)=1$ | $\delta^{\prime}(q,B\\!\mid\\!q,B,-1)=1$
$\delta^{\prime}([qa],\$\\!\mid\\!q,\$,-1)=\delta(q,\$,a\\!\mid\\!q,\lambda)$ ($a\neq\bot$) |
$\delta^{\prime}(q^{\prime}_{0},{|}\\!\\!\mathrm{c}\\!\mid\\![p\bot],{|}\\!\\!\mathrm{c},+1)=\delta(q_{0},{|}\\!\\!\mathrm{c},\bot\\!\mid\\!p,\bot)$ |  $\delta^{\prime}(q^{\prime}_{0},{|}\\!\\!\mathrm{c}\\!\mid\\![pa],{|}\\!\\!\mathrm{c},+1)=\delta(q_{0},{|}\\!\\!\mathrm{c},\bot\\!\mid\\!p,a\bot)$.

Note that $\bar{q}$ and $\bar{p}$ are new inner states not in $Q$, which
respectively correspond to $q$ and $p$ and that $q_{h}$ is a member of
$Q_{halt}$. The above transitions indicate that the new 2-lpa satisfies all
the requirements stated in the proposition.

Concerning the runtime of $N$, we note that the tape head always advances
toward $\$$, except that, to erase a symbol in $\Gamma_{1}$, it moves
backwards, changes the first encountered non-blank symbol to $B$, and returns.
After reading $\$$, the tape head simply moves to the left to
${|}\\!\\!\mathrm{c}$. Thus, the average number of steps is upper bounded by
$O(|x|^{2})$ multiplied by the average runtime of $M$ on $x$. ∎

We then return to Theorem 3.5 and provide its proof, based on Lemmas 3.7 and
3.8.

Proof of Theorem 3.5.  (1) It is rather easy to simulate a 2pfa on a 1-lpa
that behaves like the 2pfa but changes each input symbol $\sigma$ to its
corresponding symbol $\sigma^{\prime}$. On the contrary, we can simulate a
1-lpa $M$ by the following 2pfa $N$. A key idea of this simulation is that it
is possible to transform $M$ into the specific form where $M$ always rewrites
a new corresponding symbol over each distinct input symbol. Since $N$ can
remember the correspondence between input symbols and their corresponding new
symbols, whenever $N$ reads any overwritten symbol $\tau$, $N$ can translate
it back to its original input symbol $\sigma$ and then simulate $M$’s single
step of processing $\sigma$.

(2) These equalities directly come from Lemmas 3.7 and 3.8. Here, we only show
that
$1\mathrm{PPDA}_{\varepsilon}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LPA}_{\varepsilon}$
since the other equalities can be proven similarly.

Let $L$ be any language in $1\mathrm{PPDA}_{\varepsilon}$ and take a 1ppda $M$
that recognizes $L$ with error probability at most $\varepsilon\in[0,1/2)$. By
the ideal shape lemma (Lemma 2.1), $M$ can be assumed to be in an ideal shape.
We then apply Lemma 3.8 and obtain a blank-skipping $2$-lpa $N$ that simulates
$M$ with the same error probability on all inputs. Therefore, $L$ belongs to
$2\mbox{-}\mathrm{LPA}_{\varepsilon}$. Conversely, for any language $L$ in
$\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LPA}$, take a blank-skipping $2$-lpa $N$
satisfying $L=L(N)$. Lemma 3.7 implies the existence of an ideal-shape 1ppda
$M$ that is error-equivalent to $N$. We thus conclude that $L$ is in
$1\mathrm{PPDA}_{\varepsilon}$.

(3) This can be proven in a similar way as (2). $\Box$

###  3.4 Power of Limited Randomness

We will see how randomness endows enormous power to underlying limited
automata. In automata theory, the computational power of randomness was first
observed by Freivalds [2], who designed a two-way probabilistic finite
automaton that recognizes the non-regular language $\\{a^{n}b^{n}\mid
n\in\mathbb{N}\\}$ with bounded-error probability.

The language family $k\mbox{-}\mathrm{LRA}$ turns out to be relatively large.
This comes from the fact that $k\mbox{-}\mathrm{LPA}$ contains languages not
recognized by any $k$-lda for each fixed index $k\geq 2$.

###### Theorem 3.9

For any index $k\geq 2$, $k\mbox{-}\mathrm{LDA}\subsetneqq
k\mbox{-}\mathrm{LRA}\cap(k+1)\mbox{-}\mathrm{LDA}$.

Unfortunately, Theorem 3.9 is not strong enough to yield the separation of
$\omega\mbox{-}\mathrm{LDA}\neq\omega\mbox{-}\mathrm{LRA}$. We also do not
know whether or not $3\mbox{-}\mathrm{LDA}\nsubseteq 2\mbox{-}\mathrm{LRA}$ as
well as $\omega\mbox{-}\mathrm{LRA}\nsubseteq 2\mbox{-}\mathrm{LBPA}$.

Let us state the proof of Theorem 3.9. The proof utilizes example languages,
which can separate $k\mbox{-}\mathrm{LDA}$ from $(k+1)\mbox{-}\mathrm{LDA}$
for each index $k\geq 2$. Earlier, Hibbard [6] devised such an example
language for each index $k\geq 2$. In the case of $k=2$, a much simpler
example language was given in [17]. The example language $L_{k}$ given below
is, in fact, a slight modification of the one stated in [6]. An argument
similar to [6, Section 4] verifies that, for each index $k\geq 2$, the
language $L_{k}$ is included in $(k+1)\mbox{-}\mathrm{LDA}$ but outside of
$k\mbox{-}\mathrm{LDA}$.

(1) When $k=2$, $L_{2}$ denotes the language $\\{a^{n}b^{n}c,a^{n}b^{2n}d\mid
n\geq 0\\}$.

(2) Let $k\geq 3$ be any integer. We succinctly write $w_{1}$ for either $a$
or $b$ and, for any index $i\in[2,k-1]_{\mathbb{Z}}$, we write $w_{i}$ for
$a^{n_{i}}b^{m_{i}}c^{p_{i}}$ for arbitrary numbers
$n_{i},m_{i},p_{i}\in\mathbb{N}$. The desired language $L_{k}$ is composed of
all strings $w$ of the form
$w_{2}\\#w_{4}\\#\cdots\\#w_{k-2}\\#w_{k}\\#w_{k-1}\\#\cdots\\#w_{5}\\#w_{3}\\#w_{1}$
if $k$ is even, and
$w_{2}\\#w_{4}\\#\cdots\\#w_{k-1}\\#w_{k}\\#w_{k-2}\\#\cdots\\#w_{5}\\#w_{3}\\#w_{1}$
if $k$ is odd, together with the following three conditions.

  1. (i)

If $w_{1}=a$, then $n_{2}\leq p_{2}$ holds; otherwise, $m_{2}\leq p_{2}$
holds.

  2. (ii)

Let $j$ denote any index in $[3,k-1]_{\mathbb{Z}}$. If either
$n_{j-1}=p_{j-1}$ or $n_{j-1}<m_{j-1}$, then $n_{j}\leq m_{j}$ holds. If
either $n_{j-1}<p_{j-1}$ or $n_{j-1}=m_{j-1}$, then $n_{j}\leq p_{j}$ holds.

  3. (iii)

If $n_{k-1}=p_{k-1}$, then $n_{k}=m_{k}$ holds. If $n_{k-1}<p_{k-1}$, then
$n_{k}<p_{k}$ holds. If $n_{k-1}=m_{k-1}$, then $n_{k}=p_{k}$. If
$n_{k-1}<m_{k-1}$, then $n_{k}<m_{k}$ holds.

Proof of Theorem 3.9.  We first show the case of $k=2$, that is, $L_{2}\in
2\mbox{-}\mathrm{LRA}\cap 3\mbox{-}\mathrm{LDA}$ but $L_{2}\notin
2\mbox{-}\mathrm{LDA}$. Clearly, $L_{2}$ is in $3\mbox{-}\mathrm{LDA}$ and it
is also known that $L_{2}\notin\mathrm{DCFL}$ [32]. Since
$\mathrm{DCFL}=2\mbox{-}\mathrm{LDA}$ [17], $L_{2}\notin
2\mbox{-}\mathrm{LDA}$ follows. It thus suffices to show that $L_{2}\in
1\mathrm{RPDA}_{1/2}$ because Theorem 3.5 implies $L_{2}\in
2\mbox{-}\mathrm{LRA}$. Consider the following 1ppda. On input $x$, choose $c$
and $d$ with equiprobability $1/2$ and let $z$ denote the chosen symbol. When
$z=c$, check deterministically whether $x=a^{n}b^{n}c$; in contrast, when
$z=d$, check whether $x=a^{n}b^{2n}d$. If this is the case, then accept $x$;
otherwise, reject it. The probability that $x$ is accepted is exactly $1/2$ if
$x\in L_{2}$. On the contrary, if $x\notin L_{2}$, then $x$ is rejected with
probability $1$. Hence, $L_{2}$ belongs to $1\mathrm{RPDA}_{1/2}$, as
requested.

Let $k\geq 3$ and consider $L_{k}$. Since
$L_{k}\in(k+1)\mbox{-}\mathrm{LDA}-k\mbox{-}\mathrm{LDA}$ [6], it suffices to
prove that $L_{k}\in k\mbox{-}\mathrm{LRA}$. We focus on the case that $k$ is
odd. Take a $(k+1)$-lda $M_{k}$ that recognizes $L_{k}$. We further assume
that $M_{k}$ first checks whether $w_{1}=a$ or $w_{1}=b$ by moving its tape
head to the $w_{1}$-region and that, once $M_{k}$ leaves the $w_{1}$-region,
the tape head never returns to this region.

Let us consider a new machine $N_{k}$ defined as follows. On input $w$ of the
form $w_{2}\\#w_{4}\\#\cdots\\#w_{k-1}\\#w_{k}\\#w_{k-2}\\#\cdots
w_{3}\\#w_{1}$, choose an element $z\in\\{a,b\\}$ with equal probability and
then simulate $M_{k}$ from the moment when its tape head moves back from
$w_{1}$ toward the $w_{2}$-region to start checking that
$w_{2},w_{3},\ldots,w_{k}$ satisfy Conditions (ii)–(iii). If $M_{k}$
eventually rejects $w$, then $N_{k}$ also rejects it. Otherwise, $N_{k}$ moves
its tape head to the $w_{1}$-region and check if $w_{1}=z$. If so, then
$N_{k}$ accepts $w$; otherwise, $N_{k}$ rejects it. Since $M_{k}$ is
deterministic, if $w\in L_{k}$, then $N_{k}$ accepts $w$ with probability
$1/2$; otherwise, $N_{k}$ rejects it with probability $1$. It is also clear
that $N_{k}$ is a $k$-limited automaton. Therefore, $N_{k}$ is a $k$-lra and,
since $L_{k}=L(N_{k})$, $L_{k}$ belongs to $k\mbox{-}\mathrm{LRA}$.

The other case that $k$ is even is similarly treated. $\Box$

If we restrict the values of transition probabilities, then the associated
bounded-error 2pfa’s are, in general, significantly less powerful. As such an
example, Wang [23] earlier showed that $\mathrm{DCFL}$ contains all languages
recognized with bounded-error probability by 2pfa’s having _rational
transition probabilities_. For notational convenience, we denote by
$k\mbox{-}\mathrm{LBPA}^{(rat)}$ the subclass of $k\mbox{-}\mathrm{LBPA}$
defined by $k$-lpa’s using only rational transition probabilities. Theorem
3.5(1) thus implies the following.

###### Corollary 3.10

$1\mbox{-}\mathrm{LBPA}^{(rat)}\subseteq\mathrm{DCFL}\subsetneqq
2\mbox{-}\mathrm{LRA}$.

###  3.5 Collapses of $\omega$-LPFA, $\omega$-LRA, and $\omega$-LUA

Certain models of limited automata can reduce the number of permitted tape-
symbol modifications. For instance, any $k$-lna with $k\geq 2$ has its
recognition-equivalent $2$-lna, leading to the collapse of
$\omega\mbox{-}\mathrm{LNA}$ down to $2\mbox{-}\mathrm{LNA}$ [6]. Here, we
intend to seek similar collapses for other models of limited automata. In
particular, we wish to demonstrate the collapses of
$\omega\mbox{-}\mathrm{LPA}$ to $2\mbox{-}\mathrm{LPA}$,
$\omega\mbox{-}\mathrm{LRA}$ to $2\mbox{-}\mathrm{LRA}$, and
$\omega\mbox{-}\mathrm{LUA}$ to $2\mbox{-}\mathrm{LUA}$ (where
$2\mbox{-}\mathrm{LUA}$ equals $\mathrm{UCFL}$ by Proposition 3.4 and Theorem
3.5). This result hints the robustness of the language families
$2\mbox{-}\mathrm{LPA}$, $2\mbox{-}\mathrm{LRA}$, and $2\mbox{-}\mathrm{LUA}$.

###### Theorem 3.11

$\omega\mbox{-}\mathrm{LPA}=2\mbox{-}\mathrm{LPA}$,
$\omega\mbox{-}\mathrm{LRA}=2\mbox{-}\mathrm{LRA}$, and
$\omega\mbox{-}\mathrm{LUA}=2\mbox{-}\mathrm{LUA}$.

Since $\omega\mbox{-}\mathrm{LDA}$ is contained in both
$\omega\mbox{-}\mathrm{LRA}$ and $\omega\mbox{-}\mathrm{LUA}$, and
$\omega\mbox{-}\mathrm{LBPA}$ is also contained in
$\omega\mbox{-}\mathrm{LPA}$, Theorem 3.11 further implies the following
containments.

###### Corollary 3.12

$\omega\mbox{-}\mathrm{LDA}\subseteq 2\mbox{-}\mathrm{LRA}\cap
2\mbox{-}\mathrm{LUA}$ and $\omega\mbox{-}\mathrm{LBPA}\subseteq
2\mbox{-}\mathrm{LPA}$.

Hereafter, we intend to prove Theorem 3.11. We remark that an argument given
in the proof of the theorem further proves Hibbard’s collapse result of
$\omega\mbox{-}\mathrm{LNA}=2\mbox{-}\mathrm{LNA}$. The proof requires three
fundamental relationships between $k\mbox{-}\mathrm{LPA}$ and
$(k+1)\mbox{-}\mathrm{LPA}$, between $k\mbox{-}\mathrm{LRA}$ and
$(k+1)\mbox{-}\mathrm{LRA}$, and between $(k+1)\mbox{-}\mathrm{LUA}$ and
$k\mbox{-}\mathrm{LUA}$ regarding “reversal” for any index $k\geq 2$.

Let us consider any multi-valued total function
$f:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$, for two alphabets $\Sigma_{1}$ and
$\Sigma_{2}$, witnessed by a certain nondeterministic Turing machine (not
necessarily limited to a 1nfa) $M_{f}$ with a write-once output tape, provided
that $M_{f}$ moves to $\$$ and enters a fixed accepting state, say, $q_{acc}$
unless $M_{f}$ enters any rejecting state to invalidate the existing strings
produced on the output tape. For any probabilistic Turing machine $M$ over
$\Sigma_{2}$, we use the notation $L_{f,M}$ for the special language
$\\{x\in\Sigma_{1}^{*}\mid\sum_{y\in f(x)}{\mathrm{Prob}}_{M}[\text{ $M$
accepts $y$ }]>\frac{1}{2}|f(x)|\\}$. Let us recall the function class
$\mathrm{rtNFAMV}_{t}$ from Section 2.2. By abusing the notation, we write
$k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}$ to denote the set of all such
$L_{f,M}$’s for any $f\in\mathrm{rtNFAMV}_{t}$ and any $k$-lpa $M$. When $M$
is a $k$-lra, we choose an arbitrary constant $\eta\in(0,1/2)$ and define
$L_{f,M,\eta}$ as $\\{x\in\Sigma_{1}^{*}\mid\sum_{y\in
f(x)}{\mathrm{Prob}}_{M}[\text{ $M$ accepts $y$ }]>\eta|f(x)|\\}$. In the case
where $M$ is a $k$-lna, by contrast, we set $L_{f,M}$ to be
$\\{x\in\Sigma_{2}^{*}\mid\exists y\in f(x)[\text{ $M$ accepts $y$ }]\\}$ and
write $k\mbox{-}\mathrm{LUA}\circ\mathrm{rtNFAMV}_{t}$ for the collection of
all such $L_{f,M}$’s.

We argue that $k\mbox{-}\mathrm{LPA}$ as well as $k\mbox{-}\mathrm{LRA}$ and
$k\mbox{-}\mathrm{LUA}$ is “invariant” with an application of
$\mathrm{rtNFAMV}_{t}$-functions in the following sense.

###### Lemma 3.13

For any index $k\geq 2$,
$k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}=k\mbox{-}\mathrm{LPA}$. The
same equality holds for $k\mbox{-}\mathrm{LRA}$ and $k\mbox{-}\mathrm{LUA}$ as
well.

###### Proof.

Let $k\geq 2$. We first concentrate on the case of $k\mbox{-}\mathrm{LPA}$. It
is obvious that $k\mbox{-}\mathrm{LPA}\subseteq
k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}$ by considering the _identity
function_ in $\mathrm{rtNFAMV}_{t}$. Thus, we need to prove only the opposite
inclusion. Take a multi-valued total function $f$ in $\mathrm{rtNFAMV}_{t}$
and a $k$-lpa $M$, and consider the associated language $L_{f,M}$. There
exists a real-time 1nfa $M_{f}$ with a write-once output tape that computes
$f$. Let us consider the following probabilistic machine $N$. Starting with
input $x$, $N$ runs $M_{f}$ and, along each computation path of $M_{f}$,
whenever $M_{f}$ produces one nonempty output symbol $\sigma$,$N$ runs $M$ to
process $\sigma$. If $M_{f}$ enters an accepting state in the end, then $N$
does the same after processing the last output symbol of $f$; otherwise, $N$
enters both accepting and rejecting states with equiprobability after
finishing the processing of $M_{f}$’s output symbols. Note that $N$ is a
$k$-lpa because $M_{f}$ does not need any memory space and $N$ can process
each output symbol of $M_{f}$ without using $M_{f}$’s output tape. It thus
follows that $p_{acc,N}(x)=\alpha_{M}(x)\sum_{y\in
f(x)}\frac{p_{acc,M}(y)}{|f(x)|}+\frac{1}{2}(1-\alpha_{M}(x))$, where
$\alpha_{M}(x)$ is the ratio of the number of accepting paths out of the total
computation paths of $M$ on $x$. If $x\in L_{f,M}$, then we obtain
$p_{acc,N}(x)>\frac{1}{2}$; otherwise, $p_{acc,N}(x)\leq\frac{1}{2}$ follows.
We thus conclude that $N$ recognizes $L_{f,M}$ with unbounded-error
probability. Therefore, $L_{f,M}$ belongs to $k\mbox{-}\mathrm{LPA}$.

By slightly modifying the above argument, we can show the lemma for
$k\mbox{-}\mathrm{LRA}$ and $k\mbox{-}\mathrm{LUA}$. ∎

Consider any $k$-lpa $M$ used in the aforementioned definition of
$k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}$. If we feed such an $M$ with
the reverses $x^{R}$ of inputs $x$, then we obtain
$k\mbox{-}\mathrm{LPA}^{R}\circ\mathrm{rtNFAMV}_{t}$. We show the following
key relationships between $(k+1)\mbox{-}\mathrm{LPA}$ and
$k\mbox{-}\mathrm{LPA}^{R}$, between $(k+1)\mbox{-}\mathrm{LRA}$ and
$k\mbox{-}\mathrm{LRA}^{R}$, and between $(k+1)\mbox{-}\mathrm{LUA}$ and
$k\mbox{-}\mathrm{LUA}^{R}$.

###### Lemma 3.14

For any $k\geq 2$,
$k\mbox{-}\mathrm{LPA}^{R}\circ\mathrm{rtNFAMV}_{t}=(k+1)\mbox{-}\mathrm{LPA}$.
The same equality also holds between $k\mbox{-}\mathrm{LRA}^{R}$ and
$(k+1)\mbox{-}\mathrm{LRA}$ and between $k\mbox{-}\mathrm{LUA}^{R}$ and
$(k+1)\mbox{-}\mathrm{LUA}$.

###### Proof.

Fix $k\geq 2$. Firstly, we intend to verify the lemma for
$k\mbox{-}\mathrm{LPA}$ and then explain how to modify the proof for
$k\mbox{-}\mathrm{LRA}$ as well as $k\mbox{-}\mathrm{LUA}$. For readability,
we split the proof into two different parts.

(1) We first plan to derive the inclusion of
$(k+1)\mbox{-}\mathrm{LPA}\subseteq
k\mbox{-}\mathrm{LPA}^{R}\circ\mathrm{rtNFAMV}_{t}$. Let $L$ be any language
in $(k+1)\mbox{-}\mathrm{LPA}$ witnessed by a $(k+1)$-lpa
$M=(Q_{M},\Sigma,\\{{|}\\!\\!\mathrm{c},\$\\},\\{\Gamma^{(i)}_{M}\\}_{i\in[k]},\delta_{M},q_{0},Q_{acc},Q_{rej})$.
Let $\Gamma^{(0)}_{M}=\Sigma$. For convenience, assume that $M$ takes $q_{0}$
only at the first step and that $M$ halts after its tape head scans $\$$ (but
this is not necessarily the first time).

To simulate the behavior of $M$, we introduce a notion of _cell state_. A cell
state is of the form $(d,q,\sigma\\!\mid\\!\tau,p,e\\!\mid\\!h)$, which
indicates that a tape head of $M$ enters the current tape cell, say, $\ell$
from direction $d\in\\{L,R,N\\}$ (where $L$ means the left, $R$ means the
right, and $N$ refers to the start cell) in inner state $q$, reads tape symbol
$\sigma$, changes $q$ to $p$ and $\sigma$ to $\tau$, and leaves cell $\ell$ in
direction $e\in\\{L,R\\}$. As for $h\in(Q^{2}\times\Gamma)\cup\\{\lambda\\}$,
if $(d,e)=(L,L)$, then $M$ makes a left turn, and thus $h$ indicates the
information on $M$’s situation at the time when $M$ visits cell $\ell$ for the
3rd time. If $d\neq R$ and $e=R$, then $h$ must be $\lambda$. Along each
computation path of $M$, the first “traverse” of $M$’s tape head from left to
right uniquely determines a series of such cell states.

Figure 3: The simulation of the first and the second traverses of a tape head
of $M$.

As the first step, we want to define a multi-valued total function $g$
computed by a real-time 1nfa $M_{g}$ that simulates the first traverse of
$M$’s tape head. This function $g$ nondeterministically describes the
“actions” of $M$ while it reads input symbols for the first time. On an input,
$M_{g}$ partly simulates $M$ symbol by symbol but $M_{g}$’s tape head moves
only to the right. Consider tape cell, say, $\ell$ and let $\sigma$ be the
input symbol in $\check{\Sigma}$ ($=\Sigma\cup\\{{|}\\!\\!\mathrm{c},\$\\}$)
written in cell $\ell$. For the ease of description of the construction of
$M_{g}$, we arbitrarily fix a computation path of $M$ and explain how to
operate $M_{g}$ along this particular computation path (as if $M$ works
deterministically). There are several cases to treat separately. At any
moment, if $M$ enters any halting state, then $M_{g}$ does the same to
invalidate the current output strings since this situation suggest that the
simulation of $M$ by $M_{g}$ along this particular computation path is wrong.

(i) Consider the case $M$ is in initial state $q_{0}$ reading
${|}\\!\\!\mathrm{c}$. If $M$ changes $q_{0}$ to $p$ and leaves cell $\ell$ to
the right, then $M_{g}$ writes down
$(N,q_{0},{|}\\!\\!\mathrm{c}\mid{|}\\!\\!\mathrm{c},p,R\\!\mid\\!\lambda)$ to
its output tape. We store $p$ in $M_{g}$’s internal memory and move the tape
head of $M$ to the right in inner state $p$.

(ii) Consider the case where $M$’s tape head enters cell $\ell$ for the first
time from the left and reads $\sigma\in\check{\Sigma}$ in inner state $q\in
Q-\\{q_{0}\\}$ but $M$ does not make any left turn. Let the memory of $M_{g}$
contain $q$. If $M$ changes $q$ to $p$, changes $\sigma$ to $\tau$, and leaves
cell $\ell$ to the right, then $M_{g}$ writes down
$(L,q,\sigma\mid\tau,p,R\\!\mid\\!\lambda)$ on its output tape. We remember
$p$ and move the tape head of $M$ to the right in inner state $p$.

(iii) Assume that $M$ enters cell $\ell$ for the first time from the left and
makes a left turn. Assume that $q$ is in $M_{g}$’s memory. In this case, we
“skip” many subsequent moves of $M$ and “jump” into $M$’s step at which $M$
returns to cell $\ell$ for the second time. See Fig. 3. We guess a triplet
$(t,r,a)$ satisfying $(r,a,R)\in\delta_{M}(t,\tau)$. If there is no such
triplet, then $M_{g}$ enters a rejecting state to invalidate the existing
output strings. If $M$ changes $q$ to $p$, then $M_{g}$ writes down
$(L,q,\sigma\\!\mid\\!\tau,p,L\\!\mid\\!t,r,a)$ and remembers $r$. We then
move the tape head of $M$ to the right in inner state $r$.

(iv) Consider the case where cell $\ell$ contains $\$$ and $M$ enters cell
$\ell$ for the first time from the left. Assume that $q$ is in the memory of
$M_{g}$. If $M$ changes $q$ to $p$ and moves backward, then $M_{g}$ produces
$(L,q,\$\\!\mid\\!\$,p,L\\!\mid\\!\lambda)$ and halts by entering a designated
accepting state $q_{acc}$. If $M$ processes the endmarker $\$$ and terminates,
then $M_{g}$ produces $(L,q,\$\\!\mid\\!\$,p,R\\!\mid\\!\lambda)$ and halts in
inner state $q_{acc}$.

Clearly, $M_{g}$ is a real-time 1nfa, and therefore $g$ belongs to
$\mathrm{rtNFAMV}_{t}$. Given any index $\ell\in[0,n+1]_{\mathbb{Z}}$, we call
cell $\ell$ a _turning point_ if $M$ makes a left turn at cell $\ell$ during
the first “traverse”.

As the second step, we wish to define a $k$-lpa $N$ that takes an input
provided by $g$ and simulates $M$. For readability, we describe the behavior
of $N$ starting at the left end of the tape. As before, we fix an arbitrary
computation path of $M$ and assume that $M_{g}$ operates along this particular
computation path associated with $g$’s outcome
$(N,q_{0},{|}\\!\\!\mathrm{c}\mid{|}\\!\\!\mathrm{c},p,R\\!\mid\\!\lambda)w(L,q,\$\mid\$,p,d\\!\mid\\!h)$,
where $d\in\\{L,R\\}$ and $w$ is a (possibly empty) series of cell states.
Assume that $w$ is a length-$n$ sequence $w_{1}w_{2}\cdots w_{n}$ of cell
states. For convenience, we set
$w_{0}=(N,q_{0},{|}\\!\\!\mathrm{c}\mid{|}\\!\\!\mathrm{c},p,R\\!\mid\\!\lambda)$
and $w_{n+1}=(L,q,\$\mid\$,p,d\\!\mid\\!h)$. The input to $N$ is thus
$(w_{0}ww_{n+1})^{R}$, which is abbreviated as $\widetilde{w}^{R}$.

Given $\tilde{w}^{R}$, $N$ starts to simulate $M$’s second “traverse” from
left to right until the next turning point. While $M$ simulates $M$’s second
traverse, if $N$ encounters the next turning point at cell $\ell$, instead of
continuing the current simulation of $M$, $N$ “jumps” to the time of the left
turn and resumes the simulation of $M$’s moves from this point. Even if $M$
makes a right turn at cell $\ell$ at its 2nd visit, $N$ continues the
simulation of $M$’s moves. A more detailed simulation process is described
below. Let $\ell$ denote any cell index in $[n]$.

(i′) The machine $N$ begins in its initial state $q^{\prime}_{0}$, scanning
$w_{n+1}=(L,q,\$\mid\$,p,L\\!\mid\\!\lambda)$ written in the rightmost cell of
its input tape. If $M$ makes a transition of the form
$(s,\$,L)\in\delta_{M}(p,\$)$, then $N$ writes down
$[\>\begin{subarray}{c}w_{n+1}\\\ \$\end{subarray}]$ into this cell, remembers
$s$ in $N$’s memory, and moves to the left.

(ii′) Assume that $N$’s tape head is scanning
$w_{\ell}=(L,q,\sigma\mid\tau,p,R\\!\mid\\!\lambda)$ with $s$ in its memory.
If $M$ follows a transition of the form $(r,a,d)\in\delta_{M}(s,\tau)$ along
the current computation path with $d\in\\{L,R\\}$, then $N$ writes down
$[\>\begin{subarray}{c}w_{\ell}\\\ a\end{subarray}]$ into this cell, remembers
$r$, and moves in direction $d$.

(iii′) Assume that $\sigma\neq\$$ and $N$’s tape head is scanning
$w_{\ell}=(L,q,\sigma\\!\mid\\!\tau,p,L\\!\mid\\!t,r,a)$ with $s$ in the
memory. This implies that $M$ makes a left turn at cell $\ell$ during the
first traverse and that $M$ returns to cell $\ell$ in inner state $t$ during
the second traverse, and in inner state $s$ during the 3rd traverse. If $M$
makes a transition “$(u,b,L)\in\delta_{M}(s,a)$”, then $N$ writes
$[\>\begin{subarray}{c}w_{\ell}\\\ (u,s,a)\end{subarray}]$ over $w_{\ell}$,
remembers $p$, and moves to the left.

(iv′) Assume that $N$ scans $[\>\begin{subarray}{c}w_{\ell}\\\
a\end{subarray}]$ with $s$ in the memory for symbol $a\in\Gamma^{(i)}_{M}$
with $i\in[2,k]_{\mathbb{Z}}$. Note that $N$ has already visited this cell at
most $i-1$ times if $i<k$. If $M$ follows a transition
“$(r,b,d)\in\delta_{M}(s,a)$” with direction $d\in\\{L,R\\}$, then $N$ writes
down $[\>\begin{subarray}{c}w_{\ell}\\\ b\end{subarray}]$ into this cell,
remembers $r$, and moves in direction $d$.

(v′) Assume that $N$ enters cell $\ell$ from the left and scans
$[\>\begin{subarray}{c}w_{\ell}\\\ (u,s,b)\end{subarray}]$ with $z$ in the
memory. Since this is a turning point, we assume that $w_{\ell}$ has the form
$(L,q,\sigma\\!\mid\\!\tau,p,L\\!\mid\\!t,r,a)$. Since $z\neq t$ leads to a
discrepancy, we need to consider only the case of $z=t$. The machine $N$ then
writes down $[\>\begin{subarray}{c}w_{\ell}\\\ b\end{subarray}]$, remembers
$u$, and moves to the left.

(vi′) Assume that $N$ scans
$w_{0}=(N,q_{0},{|}\\!\\!\mathrm{c}\\!\mid\\!{|}\\!\\!\mathrm{c},p,R\\!\mid\\!\lambda)$
with $s$ in the memory. If $M$ makes a transition of the form
$(r,{|}\\!\\!\mathrm{c},R)\in\delta_{M}(s,{|}\\!\\!\mathrm{c})$, then $N$
writes down $[\>\begin{subarray}{c}w_{0}\\\
{|}\\!\\!\mathrm{c}\end{subarray}]$, remembers $r$, and moves to the right.

Since $g$’s outcomes contain “guessed” results, whenever the above simulation
process discovers any discrepancy on these outcomes, $N$ immediately enters
both accepting and rejecting states with equal probability. This cancels out
all erroneous computations of $M_{g}$. When $N$ correctly terminates, it
successfully simulates $M$’s computation with the help of $g$. By the
description of $N$, it follows that $N$ is indeed a $k$-lpa.

(2) Secondly, we wish to show the opposite inclusion, namely,
$k\mbox{-}\mathrm{LPA}^{R}\circ\mathrm{rtNFAMV}_{t}\subseteq(k+1)\mbox{-}\mathrm{LPA}$.
Let $M$ denote a $k$-lpa and let $f$ be a function in $\mathrm{rtNFAMV}_{t}$
witnessed by a certain 1nfa, say, $M_{f}$. We write $M^{R}$ to indicate that
$M$ takes the reverse $y^{R}$ of any input $y$. We define
$L_{f,M^{R}}=\\{x\in\Sigma^{*}\mid\sum_{y\in
f(x)}{\mathrm{Prob}}_{M^{R}}[\text{ $M^{R}$ accepts $y$
}]>\frac{1}{2}|f(x)|\\}$. Our goal is to verify that
$L_{f,M^{R}}\in(k+1)\mbox{-}\mathrm{LPA}$. Consider the new machine $N$ that
works as follows. On input $x$ given to a tape, run $M_{f}$ on $x$ by
replacing $x$ with $M_{f}$’s output strings $y$ produced along computation
paths. Once ${|}\\!\\!\mathrm{c}{y}\$$ is written on the tape, run $M^{R}$ on
$({|}\\!\\!\mathrm{c}y\$)^{R}$ by moving a tape head leftwards starting at
$\$$. Since $M$ is $k$-limited, $N$ must be $(k+1)$-limited. We thus conclude
that $L_{f,M^{R}}\in(k+1)\mbox{-}\mathrm{LPA}$. ∎

Finally, the proof of Theorem 3.11 is given with the help of Lemmas 3.13 and
3.14.

Proof of Theorem 3.11.  By taking “reversal” of Lemma 3.14, we obtain
$(k+1)\mbox{-}\mathrm{LPA}^{R}=k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}^{R}$.
From Lemma 3.14 again, it also follows that
$(k+2)\mbox{-}\mathrm{LPA}=(k+1)\mbox{-}\mathrm{LPA}^{R}\circ\mathrm{rtNFAMV}_{t}$.
Combining these two equalities, we conclude that (*)
$(k+2)\mbox{-}\mathrm{LPA}\subseteq(k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}^{R})\circ\mathrm{rtNFAMV}_{t}$.
We then claim the following inclusion, which is not “trivial” due to our
nonstandard use of “$\circ$”.

###### Claim 1

$(k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}^{R})\circ\mathrm{rtNFAMV}_{t}\subseteq
k\mbox{-}\mathrm{LPA}\circ(\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t})$.

###### Proof.

Take a function $g\in\mathrm{rtNFAMV}_{t}$ and a probabilistic Turing machine
$N$ such that the language $L_{g,N}$ belongs to
$(k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}^{R})\circ\mathrm{rtNFAMV}_{t}$.
This machine $N$ is further assumed to characterize a language $L_{f^{R},M}$
as $L(N)=L_{f^{R},M}$ by a certain function $f\in\mathrm{rtNFAMV}_{t}$ and a
certain $k$-lpa $M$. Associated with this $f$, we take a 1nfa $M_{f^{R}}$ with
a write-once output tape that computes $f^{R}$. Since $N$ recognizes
$L_{f^{R},M}$, we focus our attention on the machine $N$ that firstly
simulates $M_{f^{R}}$ to obtain its outcomes and then runs $M$ on the
outcomes.

For readability, we write $L^{\prime}$ for $L_{g,N}$. Next, we intend to
verify that this language $L^{\prime}$ is in fact in
$k\mbox{-}\mathrm{LPA}\circ(\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t})$.
For this purpose, we need to define a function
$h\in\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t}$ and another $k$-lpa
$K$ that force $L_{h,K}$ to match $L^{\prime}$.

Let us consider the following 1nfa $M^{\prime}$. Given an input $y^{R}$ of
length $n$, while $M^{\prime}$ reads $y^{R}$, $M^{\prime}$ guesses a
length-$n$ string $z=z_{1}z_{2}\cdots z_{n-1}z_{n}$ symbol by symbol and
produces $z_{1}z_{2}\cdots z_{n-1}$ onto its output tape. Simultaneously,
$M^{\prime}$ runs $M_{f^{R}}$ on $y$ to obtain its outcomes, say,
$z^{\prime}$. If $z=z^{\prime}$ and $M_{f^{R}}$ enters an accepting state,
then we set $a=acc$; otherwise, we set $a=rej$. Finally, $M^{\prime}$ writes
down $[\>\begin{subarray}{c}z_{n}\\\ a\end{subarray}]$ on the output tape and
enters an accepting state. Note that the outcomes of $M^{\prime}$ are the
strings of the form $z_{1}z_{2}\cdots z_{n_{1}}[\>\begin{subarray}{c}z_{n}\\\
a\end{subarray}]$. Now, we define $f_{+}^{R}(y)$ to be the function computed
by $M^{\prime}$. The desired function $h$ is then set as
$h(x)=\\{[\>\begin{subarray}{c}y\\\ z\end{subarray}]\mid y\in g(x),z\in
f_{+}^{R}(y)\\}$ for any $x$. Next, we define the desired $k$-lpa $K$. Given
an input $u$ of the form $[\>\begin{subarray}{c}y\\\ z\end{subarray}]$ with
$z=z_{1}z_{2}\cdots z_{n_{1}}[\>\begin{subarray}{c}z_{n}\\\ a\end{subarray}]$,
if $a=rej$, then we enter both an accepting state and a rejecting state with
equiprobability. Otherwise, we simulates $M$ on $z_{1}z_{2}\cdots z_{n}$ using
only the lower track of the tape (and the upper track is intact).

Since $M^{\prime}$ guesses all length-$n$ strings $z$ and never invalidates
their outcomes $z^{\prime}$, we obtain
$|f_{+}^{R}(y)|=|f_{+}^{R}(y^{\prime})|$ for any $y,y^{\prime}\in g(x)$. It
also follows that, for any $y\in g(x)$, since $|f^{R}(y)|=|f^{R}_{+}(y)|$,
${\mathrm{Prob}}_{N}[\text{ $N$ accepts $y$ }]$ equals $\sum_{z\in
f^{R}(y)}{\mathrm{Prob}}_{M}[\text{ $K$ accepts $[\>\begin{subarray}{c}y\\\
z\end{subarray}]$ }]\cdot\frac{1}{|f_{+}^{R}(y)|}$. Since
$|h(x)|=|g(x)||f_{+}^{R}(y)|$ for any $y\in g(x)$, we conclude that
$\sum_{y\in g(x)}{\mathrm{Prob}}_{N}[\text{ $N$ accepts $y$
}]\cdot\frac{1}{|g(x)|}$ coincides with $\sum_{y\in g(x)}\sum_{z\in
f^{R}(y)}{\mathrm{Prob}}_{K}[\text{ $K$ accepts $[\>\begin{subarray}{c}y\\\
z\end{subarray}]$ }]\cdot\frac{1}{|g(x)||f_{+}^{R}(y)|}$, which is equal to
$\sum_{[\>\begin{subarray}{c}y\\\ z\end{subarray}]\in
h(x)}{\mathrm{Prob}}_{K}[\text{ $K$ accepts $[\>\begin{subarray}{c}y\\\
z\end{subarray}]$ }]\cdot\frac{1}{|h(x)|}$. This implies that
$L^{\prime}=L_{h,K}$, as requested. ∎

By applying Claim 1 to (*), we obtain $(k+2)\mbox{-}\mathrm{LPA}\subseteq
k\mbox{-}\mathrm{LPA}\circ(\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t})$.
Lemma 2.3 then leads to
$k\mbox{-}\mathrm{LPA}\circ(\mathrm{rtNFAMV}_{t}^{R}\circ\mathrm{rtNFAMV}_{t})\subseteq
k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}$. We conclude that
$(k+2)\mbox{-}\mathrm{LPA}\subseteq
k\mbox{-}\mathrm{LPA}\circ\mathrm{rtNFAMV}_{t}$. Lemma 3.13 then implies that
$(k+2)\mbox{-}\mathrm{LPA}\subseteq k\mbox{-}\mathrm{LPA}$. Since $k$ is
arbitrary with $k\geq 2$, we conclude that
$\omega\mbox{-}\mathrm{LPA}=2\mbox{-}\mathrm{LPA}$. A similar argument also
works to prove that $\omega\mbox{-}\mathrm{LRA}=2\mbox{-}\mathrm{LRA}$ and
$\omega\mbox{-}\mathrm{LUA}=2\mbox{-}\mathrm{LUA}$. $\Box$

##  4 Closure Properties of Limited Automata

The next goal of this paper is to study fundamental closure properties of
language families induced by various types of limited automata formally
defined in Section 3.1. Given a $k$-ary operation $op$ over languages, a
language family ${\cal C}$ is said to be _closed under $op$_ if, for any $k$
languages $L_{1},L_{2},\ldots,L_{k}$ in ${\cal C}$, the language
$op(L_{1},L_{2},\ldots,L_{k})$ always belongs to ${\cal C}$. We will explore
basic closure properties of $k\mbox{-}\mathrm{LRA}$, $k\mbox{-}\mathrm{LBPA}$,
and $k\mbox{-}\mathrm{LDA}$. Those properties help us show separations of the
language families in the end.

###  4.1 Case of Deterministic Limited Automata

It is well-known that $\mathrm{DCFL}$ is not closed under the following
operations: finite union, finite intersection, reversal, concatenation,
$\lambda$-free homomorphism, and Kleene star (see, e.g., [7, 22]). Since
$2\mbox{-}\mathrm{LDA}=\mathrm{DCFL}$ [17], the same non-closure properties
hold for $2\mbox{-}\mathrm{LDA}$.We wish to further expand
$2\mbox{-}\mathrm{LDA}$ to a more general $k\mbox{-}\mathrm{LDA}$ despite the
fact that $k\mbox{-}\mathrm{LDA}\neq\mathrm{DCFL}$ for all $k\geq 3$ [6].

###### Proposition 4.1

For any index $k\geq 2$, $k\mbox{-}\mathrm{LDA}$ is closed under none of the
following operations: finite union, finite intersection, reversal,
concatenation, $\lambda$-free homomorphism, and Kleene star.

###### Proof.

Since $2\mbox{-}\mathrm{LDA}=\mathrm{DCFL}$ [17] and the well-known non-
closure properties of $\mathrm{DCFL}$, the proposition is true for the case of
$k=2$. It thus suffices to discuss the case of $k\geq 3$. Recall from Section
3.4 the special language $L_{k}$ and strings $w_{1}\in\\{a,b\\}$ and
$w_{i}=a^{n_{i}}b^{m_{i}}c^{p_{i}}$ for arbitrary numbers
$n_{i},m_{i},p_{i}\geq 0$.

[finite union] Given the language $L_{k}$, for each symbol $x\in\\{a,b\\}$, we
set $L_{k}^{(x)}$ to be $\\{w\\#x\in L_{k}\mid
w=w_{2}\\#w_{4}\\#\cdots\\#w_{k-1}\\#\cdots\\#w_{5}\\#w_{3}\\}$. Since $x$ is
fixed, it is not difficult to show that $L_{k}^{(a)},L_{k}^{(b)}\in
k\mbox{-}\mathrm{LDA}$. Since $L_{k}$ equals $L_{k}^{(a)}\cup L_{k}^{(b)}$, it
follows that $L_{k}^{(a)}\cup L_{k}^{(b)}\notin k\mbox{-}\mathrm{LDA}$. We
thus conclude that $k\mbox{-}\mathrm{LDA}$ is not closed under union.

[finite intersection] This comes from the case of “finite union” together with
the fact that $k\mbox{-}\mathrm{LDA}$ is closed under complementation.

[reversal] Let us consider the reversal $L_{k}^{R}$ of the language $L_{k}$.
If $w$ denotes
$w_{2}\\#w_{4}\\#\cdots\\#w_{k-1}\\#\cdots\\#w_{5}\\#w_{3}\\#w_{1}$, then
$w^{R}$ is
$w_{1}^{R}\\#w_{3}^{R}\\#\cdots\\#w_{k-1}^{R}\\#\cdots\\#w_{4}^{R}\\#w_{2}^{R}$.
Let us consider the following machine $N$ on such an input $w^{R}$. Firstly,
$N$ checks if $w_{1}=a$ or $w_{1}=b$. If $w_{1}=a$, then $N$ moves its tape
head to the right into the $w_{2}^{R}$-region to check the correctness of
$w_{2}^{R}$. Continue checking $w_{2}^{R},w_{3}^{R},\cdots,w_{k-1}^{R}$
sequentially to determine whether $w^{R}\in L_{k}^{R}$. The case of $w_{1}=b$
can be similarly handled. Since we can implement $N$ as a $k$-lda, $L_{k}^{R}$
belongs to $k\mbox{-}\mathrm{LDA}$. Because of $L_{k}\notin
k\mbox{-}\mathrm{LDA}$, $k\mbox{-}\mathrm{LDA}$ is not closed under reversal.

[concatenation] The following argument is in essence similar to [11]. Assume
toward a contradiction that $k\mbox{-}\mathrm{LDA}$ is closed under
concatenation. Recall $L_{k}^{(a)}$ and $L_{k}^{(b)}$ for fixed symbols $a$
and $b$, defined above. Here, we further set $L^{\prime}_{k}=\\#L_{k}$
($=\\#(L_{k}^{(a)}\cup L_{k}^{(b)})$). From $L_{k}\notin
k\mbox{-}\mathrm{LDA}$, it follows that $L^{\prime}_{k}\notin
k\mbox{-}\mathrm{LDA}$. We further define $L_{k}^{(ab)}=\\#L_{k}^{(a)}\cup
L_{k}^{(b)}$ and $L_{0}$ to be the set of strings
$\\#w_{2}\\#w_{4}\\#\cdots\\#w_{k-1}\\#\cdots\\#w_{3}\\#w_{1}$, where
$w_{1}\in\\{a,b\\}$ and $w_{i}=a^{n_{i}}b^{m_{i}}c^{p_{i}}$ for certain
integers $n_{i},m_{i},p_{i}\geq 0$. The first symbol of any string of
$L_{k}^{(ab)}$ helps us distinguish between $\\#L_{k}^{(a)}$ and
$L_{k}^{(a)}$, and thus $L_{k}^{(ab)}$ falls to $k\mbox{-}\mathrm{LDA}$.
Furthermore, the language $\\#^{*}L_{k}^{(a)}$ is in $k\mbox{-}\mathrm{LDA}$.
It is also obvious that $L_{0}\in\mathrm{REG}$.

Note that $L^{\prime}_{k}$ equals $\\#^{*}L_{k}^{(ab)}\cap L_{0}$. Since
$k\mbox{-}\mathrm{LDA}$ is closed under intersection with regular languages by
Proposition 4.2, we obtain $L^{\prime}_{k}\in k\mbox{-}\mathrm{LDA}$. This is
a clear contradiction since $L^{\prime}_{k}$ is not in
$k\mbox{-}\mathrm{LDA}$.

[$\lambda$-free homomorphism] Take the languages $L_{k}^{(a)}$ and
$L_{k}^{(b)}$ defined above. Let $L^{\prime\prime}_{k}=\natural
L_{k}^{(a)}\cup\\#L_{k}^{(b)}$. Since the prefixes $\natural$ and $\\#$
respectively correspond to the suffixes $a$ and $b$, it is possible to prove
that $L^{\prime\prime}_{k}\in k\mbox{-}\mathrm{LDA}$. Consider the
$\lambda$-free homomorphism $h$ defined as $h(\natural)=\\#$ and
$h(\sigma)=\sigma$ for any $\sigma\in\\{a,b,\\#\\}$. The image
$h(L^{\prime\prime}_{k})$ matches the language $\\#(L_{k}^{(a)}\cup
L_{k}^{(b)})$, which coincides with $L^{\prime}_{k}$ as discussed above. Since
$L^{\prime}_{k}$ is not in $k\mbox{-}\mathrm{LDA}$, $k\mbox{-}\mathrm{LDA}$
cannot be closed under $\lambda$-free homomorphism.

[Kleene star] Assume that $k\mbox{-}\mathrm{LDA}$ is closed under Kleene star.
Recall $L_{k}^{(ab)}$, $L^{\prime}_{k}$, and $L_{0}$ defined above and let
$L_{\\#}=\\{\\#\\}\cup L_{k}^{(ab)}$. Since $L_{k}^{(ab)}\in
k\mbox{-}\mathrm{LDA}$, $L_{\\#}$ is also in $k\mbox{-}\mathrm{LDA}$. Consider
the Kleene closure $L_{\\#}^{*}$ of $L_{\\#}$, which is in
$k\mbox{-}\mathrm{LDA}$ by our assumption. Since $L_{0}\in\mathrm{REG}$, the
language $L=(L_{\\#})^{*}\cap L_{0}$ belongs to $k\mbox{-}\mathrm{LDA}$
because $k\mbox{-}\mathrm{LDA}$ is closed under intersection with regular
languages (in Proposition 4.2). Since $L$ is equal to
$\\#L_{k}^{(a)}\cup\\#L_{k}^{(b)}$, which is precisely $L^{\prime}_{k}$,
$L^{\prime}_{k}$ must be in $k\mbox{-}\mathrm{LDA}$, a contradiction against
$L^{\prime}_{k}\notin k\mbox{-}\mathrm{LDA}$. Therefore,
$k\mbox{-}\mathrm{LDA}$ is not closed under Kleene star. ∎

In contrast to Proposition 4.1, there are a few closure properties that
$k\mbox{-}\mathrm{LDA}$ can enjoy. Given a language $L$, its Kleene closure
$L^{*}$ is called _marked_ if the strings in $L$ end in special symbols that
appear only at the end (see, e.g., [8]). Such special symbols are called
_markers_. For instance, $(L\\#)^{*}$ is a marked Kleene closure for any
language $L$ with $\\#$ not used in $L$. We say that a language family ${\cal
C}$ is _closed under marked Kleene star_ if the marked Kleene closure of any
language in ${\cal C}$ belongs to ${\cal C}$. The closure under _marked
concatenation_ is similarly defined.

###### Proposition 4.2

Given $k\geq 2$, $k\mbox{-}\mathrm{LDA}$ is closed under the following
operations: (i) finite intersection and finite union with regular languages
and (ii) marked Kleene star and marked concatenation.

###### Proof.

(1) Consider $L=L_{1}\cap L_{2}$ for any two languages $L_{1}\in
k\mbox{-}\mathrm{LDA}$ and $L_{2}\in\mathrm{REG}$. Take a $k$-lda $M_{1}$
recognizing $L_{1}$ and a 1dfa $M_{2}$ for $L_{2}$. We then define a $k$-lpa
$N$ for $L$ as follows. On input $x$, start the simulation of $M_{1}$ on $x$.
Whenever $M_{1}$ visits a new input symbol $\sigma$, $N$ simulates $M_{2}$ on
$\sigma$ without moving its tape head. In this simulation, $N$ keeps both
inner states of $M_{1}$ and $M_{2}$ internally as its own inner states. Since
$M_{1}$ is always forced to modify input symbols at the first access, the
timing of simulation of $M_{2}$ is clear to $N$. Thus, $L$ belongs to
$k\mbox{-}\mathrm{LDA}$. The closure under finite union with regular languages
follows instantly from the equality
$k\mbox{-}\mathrm{LDA}=\mathrm{co}\mbox{-}k\mbox{-}\mathrm{LDA}$.

(2) Consider a marked Kleene closure $L^{*}$ for a language $L\in
k\mbox{-}\mathrm{LDA}$. We remark that every string in $L^{*}$ can be parsed
uniquely into a series of consecutive strings separated by designated markers.
Using this fact, we can run the following simple algorithm: on each input, run
an underlying $k$-lda by feeding parsed strings one by one until either the
$k$-lda enters a rejecting state in the midst of an input or the input is
completely processed. ∎

###  4.2 Case of Probabilistic Limited Automata

We have discussed numerous closure properties of the deterministic model of
limited automata in Section 4.1. As a followup to the previous section, let us
take a close look at various probabilistic models of limited automata and
study their closure properties. We begin with a simple consequence of Theorem
3.11 concerning “reversal”.

###### Lemma 4.3

The language families $2\mbox{-}\mathrm{LPA}$ and $2\mbox{-}\mathrm{LRA}$ are
closed under reversal.

###### Proof.

It follows from Theorem 3.11 that
$3\mbox{-}\mathrm{LPA}=2\mbox{-}\mathrm{LPA}$. Since
$2\mbox{-}\mathrm{LPA}^{R}\subseteq 3\mbox{-}\mathrm{LPA}$, we immediately
obtain $2\mbox{-}\mathrm{LPA}^{R}\subseteq 2\mbox{-}\mathrm{LPA}$. The same
argument works for $2\mbox{-}\mathrm{LRA}$ as well. ∎

Recall that $2\mbox{-}\mathrm{LDA}\wedge 2\mbox{-}\mathrm{LDA}$ is expressed
as $2\mbox{-}\mathrm{LDA}(2)$.

###### Lemma 4.4

The language family $2\mbox{-}\mathrm{LRA}$ is closed under finite union but
not under finite intersection. For the latter property, more strongly, it
follows that $2\mbox{-}\mathrm{LDA}(2)\nsubseteq 2\mbox{-}\mathrm{LRA}$.

###### finite union.

Let $h\in\mathbb{N}^{+}$ with $h\geq 2$. Take $\\{L_{i}\\}_{i\in[h]}\subseteq
2\mbox{-}\mathrm{LRA}$ and a series $\\{M_{i}\\}_{i\in[h]}$ of $k$-lpa’s, each
$M_{i}$ of which recognizes $L_{i}$ with a constant one-side error bound
$\varepsilon_{i}\in[0,1)$. Consider the following $2$-lpa $N$. On input $x$,
choose an index $i\in[h]$ with equiprobability $1/h$ and simulate $M_{i}$ on
$x$. Along each computation path of $M_{i}$, if $M_{i}$ enters an accepting
state, then $N$ enters the same accepting state; otherwise, $N$ enters a new
rejecting state. It is not difficult to see that, if
$x\in\bigcup_{i\in[h]}L_{i}$, then $N$ accepts $x$ with probability at least
$1/h$ multiplied by $1-\varepsilon_{i}$; otherwise, $N$ rejects $x$ with
probability $1$. Hence, $N$ makes one-sided error. We thus conclude that
$\bigcup_{i\in[h]}L_{i}$ belongs to $2\mbox{-}\mathrm{LRA}$.

[finite intersection] Here, we want to show that
$2\mbox{-}\mathrm{LDA}(2)\nsubseteq 2\mbox{-}\mathrm{LRA}$ because this
implies the non-closure of $k\mbox{-}\mathrm{LRA}$ under finite intersection.
Consider two languages $L^{\prime}_{1}=\\{a^{n}b^{n}c^{m}\mid n,m\geq 0\\}$
and $L^{\prime}_{2}=\\{a^{n}b^{m}c^{m}\mid n,m\geq 0\\}$ in $\mathrm{DCFL}$
($=2\mbox{-}\mathrm{LDA}$). It is well-known that $L^{\prime}_{1}\cap
L^{\prime}_{2}=\\{a^{n}b^{n}c^{n}\mid n\geq 0\\}\notin\mathrm{CFL}$. Since
$2\mbox{-}\mathrm{LRA}\subseteq\omega\mbox{-}\mathrm{LNA}=\mathrm{CFL}$, we
then obtain $L^{\prime}_{1}\cap L^{\prime}_{2}\notin 2\mbox{-}\mathrm{LRA}$.
Since $L^{\prime}_{1}\cap L^{\prime}_{2}\in 2\mbox{-}\mathrm{LDA}(2)$, it
follows that $k\mbox{-}\mathrm{LDA}(2)\nsubseteq 2\mbox{-}\mathrm{LRA}$. ∎

It is not clear that $k\mbox{-}\mathrm{LBPA}$ is closed under finite
intersection and finite union. However, by sharp contrast to Lemma 4.4,
$k\mbox{-}\mathrm{LBPA}$ is large enough to include
$k\mbox{-}\mathrm{LDA}(2)$; more strongly,
$k\mbox{-}\mathrm{LPA}_{\varepsilon}$(2) is included in
$k\mbox{-}\mathrm{LBPA}$ if $\varepsilon<1/6$.

###### Lemma 4.5

Let $k\geq 2$ and $\varepsilon\in[0,1/6)$. For any operator
$\diamond\in\\{\wedge,\vee\\}$, $k\mbox{-}\mathrm{LPA}_{\varepsilon}\diamond
k\mbox{-}\mathrm{LPA}_{\varepsilon}\subseteq k\mbox{-}\mathrm{LBPA}$ holds; in
particular, $k\mbox{-}\mathrm{LDA}(2)\subseteq k\mbox{-}\mathrm{LBPA}$.

Proof.  It suffices to consider the case of $\diamond=\vee$ because
$k\mbox{-}\mathrm{LBPA}$ is closed under complementation by Lemma 4.6. Let
$\varepsilon\in[0,1/6)$ be any error bound and let $M_{1}$ and $M_{2}$ denote
two $k$-lpa’s working over the same alphabet $\Sigma$ with error probability
at most $\varepsilon$. Note that $L=L(M_{1})\cup L(M_{2})$ is in
$k\mbox{-}\mathrm{LPA}_{\varepsilon}\vee k\mbox{-}\mathrm{LPA}_{\varepsilon}$.
Let us design a new $k$-lpa $N$ that works as follows. On input $x$, choose an
index $i\in\\{1,2\\}$ uniformly at random, run $M_{i}$ on $x$. Along each
computation path, if $M_{i}$ enters an accepting state, $N$ accepts $x$ with
probability $1$; otherwise, it accepts $x$ with probability $1/3$ and rejects
$x$ with probability $2/3$. It then follows that $p_{acc,N}(x)$ equals
$\frac{1}{2}(p_{acc,M_{1}}(x)+p_{acc,M_{2}}(x))+\frac{1}{6}(p_{rej,M_{1}}(x)+p_{rej,M_{2}}(x))$
and $p_{rej,N}(x)$ equals $\frac{1}{3}(p_{rej,M_{1}}(x)+p_{rej,M_{2}}(x))$.
Let $\varepsilon^{\prime}=\varepsilon+\frac{1}{3}$. Note that
$\frac{1}{3}\leq\varepsilon^{\prime}<\frac{1}{2}$ follows from
$\varepsilon\in[0,1/6)$. If $x\in L$, then the error probability of $N$ is at
most $2\varepsilon/3\leq\varepsilon^{\prime}$ since
$p_{rej,M_{1}}(x)+p_{rej,M_{2}}(x)\leq 1+\varepsilon$. In contrast, when
$x\notin L$, the error probability of $N$ is at most
$\varepsilon+\frac{1}{3}\leq\varepsilon^{\prime}$ since
$p_{acc,M_{1}}(x)+p_{acc,M_{2}}(x)\leq 2\varepsilon$. Therefore, $L$ is in
$k\mbox{-}\mathrm{LBPA}$.

The second part of the lemma follows immediately from the first part because
$k\mbox{-}\mathrm{LPA}_{0}=k\mbox{-}\mathrm{LDA}$ holds. $\Box$

It is, however, unknown that $k\mbox{-}\mathrm{LDA}(d)\subseteq
k\mbox{-}\mathrm{LBPA}$ holds for every index $d\geq 3$.

###### Lemma 4.6

For any $k\geq 2$, $k\mbox{-}\mathrm{LBPA}$ is closed under complementation
but $2\mbox{-}\mathrm{LRA}$ is not.

Proof.  It is not difficult to show that
$k\mbox{-}\mathrm{LBPA}=\mathrm{co}\mbox{-}k\mbox{-}\mathrm{LBPA}$ for all
indices $k\geq 2$ by swapping between accepting states and rejecting states.
By Lemma 4.4, $2\mbox{-}\mathrm{LRA}$ is closed under finite union. If
$2\mbox{-}\mathrm{LRA}=\mathrm{co}\mbox{-}2\mbox{-}\mathrm{LRA}$, then
$2\mbox{-}\mathrm{LRA}$ must be closed under finite intersection. This
contradicts the second part of Lemma 4.4. $\Box$

With the use of closure/non-closure properties of various limited automata
discussed so far, we can obtain the following class separations.

###### Theorem 4.7

For any $k\geq 2$, $k\mbox{-}\mathrm{LDA}\subsetneqq
2\mbox{-}\mathrm{LRA}\subsetneqq k\mbox{-}\mathrm{LBPA}$.

###### Proof.

All simple inclusions obviously hold. We need to show the remaining two
separations. Note that
$k\mbox{-}\mathrm{LDA}=\mathrm{co}\mbox{-}k\mbox{-}\mathrm{LDA}$ for any
$k\geq 1$. Since
$2\mbox{-}\mathrm{LRA}\neq\mathrm{co}\mbox{-}2\mbox{-}\mathrm{LRA}$ by Lemma
4.6, it follows that $k\mbox{-}\mathrm{LDA}\neq 2\mbox{-}\mathrm{LRA}$.
Similarly, from
$k\mbox{-}\mathrm{LBPA}=\mathrm{co}\mbox{-}k\mbox{-}\mathrm{LBPA}$ by Lemma
4.6, we obtain $2\mbox{-}\mathrm{LRA}\neq k\mbox{-}\mathrm{LBPA}$. ∎

##  5 A Brief Discussion and Future Directions

Since Hibbard [6] had introduced his model of _scan limited automata_ in 1967,
the model seemed to have been lost to oblivion for a few decades until
Pighizzini and Pisoni [16] rediscovered it in 2014. We have followed their
reformulation as _$k$ -limited automata_ and have examined the behaviors of
various models of limited automata, in particular, one-sided error, bounded-
error, and unbounded-error probabilistic $k$-limited automata. We then have
proven numerous properties, including closure/non-closure properties as well
as collapses and separations of language families induced by these machine
models.

For an expected further study on limited automata, we wish to list a few
interesting and important open problems, whose solutions would lead to a
significant promotion of the better understanding of the limited automata.

  1. 1.

We already know that $\omega\mbox{-}\mathrm{LNA}=2\mbox{-}\mathrm{LNA}$ [6],
$\omega\mbox{-}\mathrm{LUA}=2\mbox{-}\mathrm{LUA}$,
$\omega\mbox{-}\mathrm{LRA}=2\mbox{-}\mathrm{LRA}$, and
$\omega\mbox{-}\mathrm{LPA}=2\mbox{-}\mathrm{LPA}$ (Theorem 3.11). This fact
means that, e.g., $\\{k\mbox{-}\mathrm{LNA}\mid k\in\mathbb{N}^{+}\\}$ and
$\\{k\mbox{-}\mathrm{LPA}\mid k\in\mathbb{N}^{+}\\}$ do not form a true
(infinite) hierarchy. By contrast, as demonstrated by Hibbard,
$\\{k\mbox{-}\mathrm{LDA}\mid k\in\mathbb{N}^{+}\\}$ is indeed a true
hierarchy within $\mathrm{CFL}$. Does $\\{k\mbox{-}\mathrm{LBPA}\mid
k\in\mathbb{N}^{+}\\}$ form a true hierarchy within $2\mbox{-}\mathrm{LPA}$?
In other words, does $k\mbox{-}\mathrm{LBPA}\neq(k+1)\mbox{-}\mathrm{LBPA}$
hold for any $k\geq 2$?

  2. 2.

We have demonstrated in Lemma 4.5 that $k\mbox{-}\mathrm{LDA}(2)\subseteq
k\mbox{-}\mathrm{LBPA}$ for any $k\geq 2$. Is it possible to expand this
inclusion to $k\mbox{-}\mathrm{LDA}(d)\subseteq k\mbox{-}\mathrm{LBPA}$ for
any $d\geq 2$? If this is not the case, we can instantly conclude that
$k\mbox{-}\mathrm{LBPA}$ is not closed under intersection.

  3. 3.

Theorem 3.11 implies that
$\omega\mbox{-}\mathrm{LBPA}\subseteq\omega\mbox{-}\mathrm{LPA}=2\mbox{-}\mathrm{LPA}$.
We are wondering if this inclusion is indeed proper, namely,
$\omega\mbox{-}\mathrm{LBPA}\subsetneqq 2\mbox{-}\mathrm{LPA}$. If
$\\{k\mbox{-}\mathrm{LBPA}\mid k\in\mathbb{N}^{+}\\}$ is proven to be a true
hierarchy, then $2\mbox{-}\mathrm{LPA}$ will turn out to have a richer
structure than what we currently know.

  4. 4.

The blank-skipping property has been used in Section 3.3 to make a bridge
between pushdown automata and 2-limited automata. In particular, we have shown
in Corollary 3.6 that
$\mathrm{BPCFL}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LBPA}$ and
$\mathrm{PCFL}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LPA}$. Unfortunately,
unlike $2\mbox{-}\mathrm{LDA}$ and $2\mbox{-}\mathrm{LUA}$ (as in Proposition
3.4), we do not know that $2\mbox{-}\mathrm{LBPA}$ and $2\mbox{-}\mathrm{LPA}$
both satisfy the blank skipping property. Is it true that
$k\mbox{-}\mathrm{LBPA}=\mathrm{bs}\mbox{-}k\mbox{-}\mathrm{LBPA}$ as well as
$2\mbox{-}\mathrm{LPA}=\mathrm{bs}\mbox{-}2\mbox{-}\mathrm{LPA}$? If this is
the case, then we instantly obtain $2\mbox{-}\mathrm{LBPA}=\mathrm{BPCFL}$ and
$2\mbox{-}\mathrm{LPA}=\mathrm{PCFL}$.

  5. 5.

It is well-known that $\mathrm{DCFL}$ is not closed under intersection, that
is, $\mathrm{DCFL}\neq\mathrm{DCFL}(2)$. More strongly,
$\\{\mathrm{DCFL}(d)\mid d\in\mathbb{N}^{+}\\}$ forms an infinite hierarchy
over $\mathrm{DCFL}$ [14] (reproven in [30]). Since $k\mbox{-}\mathrm{LDA}$
extends $\mathrm{DCFL}$, we wonder if, for each fixed $k\geq 2$,
$\\{k\mbox{-}\mathrm{LDA}(d)\mid d\in\mathbb{N}^{+}\\}$ also forms an infinite
hierarchy over $k\mbox{-}\mathrm{LDA}$. Prove or disprove this statement.

  6. 6.

The definition of limited automata given in Section 3.1 uses two special
endmarkers, ${|}\\!\\!\mathrm{c}$ and $\$$. As shown in [31], these endmarkers
can be removed from many variants of pushdown automata without compromising
the computational power. It is possible to introduce the model of “no-
endmarker” limited automata by eliminating the endmarkers from the original
definition of the limited automata. Are those no-endmarker limited automata
equivalent in recognition power to the original limited automata with the
endmarkers?

  7. 7.

A _Las Vegas pushdown automaton_ is not allowed to err but is permitted to
enter a special inner state of “I don’t know” beside accepting and rejecting
states. Such Las Vegas pushdown automata were extensively discussed in [8]. A
similar motivation can drive us to explore the basic properties of Las Vegas
probabilistic models of limited automata.

  8. 8.

In the past literature, much attention has been paid to _unary languages_ ,
which are languages over single-letter alphabets, because of their distinctly
unique roles in automata theory. It is known that unary 1npda’s are equivalent
in power to unary 1dfa’s [3]. Kaņeps, Geidmanis, and Freivalds [10] argued
that unary 1ppda’s with bounded-error probability are no more powerful than
1dfa’s. Can we extend these results to unary $k$-lpa’s with bounded-error
probability?

  9. 9.

Hromkovič and Schnitger [8] discussed, using our notation, two practical
language families:
$\bigcap_{\varepsilon\in(0,1/2)}1\mathrm{PPDA}_{\varepsilon}$ and
$\bigcap_{\varepsilon\in(0,1)}1\mathrm{RPDA}_{\varepsilon}$. Similarly, we can
define
$k\mbox{-}\mathrm{LBPA}^{*}=\bigcap_{\varepsilon\in(0,1/2)}k\mbox{-}\mathrm{LPA}_{\varepsilon}$
and
$k\mbox{-}\mathrm{LRA}^{*}=\bigcap_{\varepsilon\in(0,1)}k\mbox{-}\mathrm{LRA}_{\varepsilon}$.
It is interesting to study the power and limitation of these language families
in comparison to $k\mbox{-}\mathrm{LBPA}$ and $2\mbox{-}\mathrm{LRA}$.

## References

  * [1] C. Dwork and L. Stockmeyer. Finite verifiers I: the power of interaction. Journal of the ACM 39 (1992) 800–828.
  * [2] R. Freivalds. Probabilsitic two-way machines. In the Proceedings of the 10th Symposium on Mathematical Foundations of Computer Science (MFCS’81), Lecture Notes in Computer Science, Springer, vol. 118, pp. 33–45, 1981.
  * [3] S. Ginsburg and H. G. Rice. Two families of languages related to ALGOL. Journal of the ACM 9 (1962) 350–371.
  * [4] C. Herzog. Pushdown automata with bounded nondeterminism and bounded ambiguity. Theoretical Computer Science 181 (1997) 141–157.
  * [5] F. C. Hennie. One-tape, off-line Turing machine computations. Information and Control 8 (1965) 553–578.
  * [6] T. N. Hibbard. A generalization of context-free determinism. Information and Control 11 (1967) 196–238.
  * [7] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979)
  * [8] J. Hromkovič and G. Schnitger. On probabilistic pushdown automata. Information and Computation 208 (2010) 982–995.
  * [9] J. Kaņeps and R. Freivalds. Minimal nontrivial space complexity of probabilistic one-way Turing machines. In the Proceedings of the 15th Symposium on Mathematical Foundations of Computer Science (MFCS’90), Lecture Notes in Computer Science, Springer, vol. 452, pp. 355–361, 1990.
  * [10] J. Kaņeps, D. Geidmanis, and R. Freivalds. Tally languages accepted by Monte Carlo pushdown automata. In the Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM’97), Lecture Notes in Computer Science, Springer, vol. 1269, pp. 187–195, 1997.
  * [11] M. Kutrib and A. Malcher. Reversible pushdown automata. Journal of Computer System Science 78 (2012) 1814–1827.
  * [12] M. Kutrib and M. Wendlandt. Reversible k-limited automata. Fundamenta Informaticae 155 (2017) 31–58.
  * [13] H. R. Lewis and C. H. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1st edition (1981).
  * [14] L. Y. Liu and P. Weiner. An infinite hierarchy of intersections of context-free languages. Mathematical Systems Theory 7 (1973) 185–192.
  * [15] I. I. Macarie and M. Ogihara. Properties of probabilistic pushdown automata. Theoretical Computer Science 207 (1998) 117–130.
  * [16] G. Pighizzini and A. Pisoni. Limited automata and regular languages. International Journal of Foundations of Computer Science 25 (2014) 897–916.
  * [17] G. Pighizzini and A. Pisoni. Limited automata and context-free languages. Fundamenta Informaticae 136 (2015) 157–176.
  * [18] G. Pighizzini and L. Prigioniero. Limited automata and unary languages. In the Proceedings of the 21st International Conference on Developments in Language Theory (DLT 2017), Lecture Notes in Computer Science, Springer, vol. 10396, pp. 308–319, 2017.
  * [19] K. Reinhardt and E. Allender. Making nondeterminism unambiguous. SIAM Journal on Computing 29 (2000) 1118–1131.
  * [20] R. E. Stearns and H. B. Hunt III. On the equivalence and containment problems for unambiguous regular expressions, regular grammars, and finite automata. SIAM Journal on Computing 14 (1985) 598–611.
  * [21] K. Tadaki, T. Yamakami, and J. C. H. Lin. Theory of one-tape linear-time Turing machines. Theoretical Computer Science 411 (2010) 22–43. An extended abstract appeared in the Proceedings of the 30th SOFSEM Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2004), Lecture Notes in Computer Science, Springer, vol. 2932, pp. 335–348, 2004.
  * [22] K. W. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, Dordrecht (1986)
  * [23] J. Wang. A note on two-way probabilistic automata. Information Processing Letters 43 (1992) 321–326.
  * [24] T. Yamakami. Swapping lemmas for regular and context-free languages. Manuscript, arXiv:0808.4122, 2008.
  * [25] 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 (SOFSEM 2014)Lecture Notes in Computer Science, Springer, vol. 8327, pp. 514–525, 2014. A complete version appeared at arXiv:1303.1717 .
  * [26] T. Yamakami. Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata. In the Proceedings of the 15th Italian Conference on Theoretical Computer Science (ICTCS 2014), CEUR Workshop Proceedings, vol. 1231, pp. 225–236, 2014.
  * [27] T. Yamakami. Not all multi-valued partial CFL functions are refined by single-valued functions (extended abstract). In the Proceedings of the 8th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (IFIP TCS 2014), Lecture Notes in Computer Science, Springer, vol. 8705, pp. 136–150, 2014.
  * [28] T. Yamakami. Pseudorandom generators against advised context-free languages. Theoretical Computer Science 613 (2016) 1–27.
  * [29] 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.
  * [30] T. Yamakami. Intersection and union hierarchies of deterministic context-free languages and pumping lemmas. In the Proceedings of the 14th International Conference on Language and Automata Theory and Applications (LATA 2020), Lecture Notes in Computer Science, Springer, vol. 12038, pp. 341–353, 2020.
  * [31] T. Yamakami. The no endmarker theorem for one-way probabilistic pushdown automata. Manuscript, arXiv:2111.02688, 2021.
  * [32] S. Yu. A pumping lemma for deterministic context-free languages. Information Processing Letters 31 (1989) 47–51.