Restarting automata were introduced in [3] as a linguistically motivated model of automata that enables to study so-called analysis by reduction of a natural language. An overview of several variants of the model can be found in [6].

The original model of restarting automata denoted as R-automaton is a finite state machine equipped with a read/write window of a fixed length k that can move over a flexible tape. The word on its tape is always delimited by a pair of sentinels | c and $. The automaton works in cycles. Each cycle starts in the initial state with the window on the left end of the tape so it scans the left sentinel | c and the first k −1 symbols of the current tape contents, or the rest of the tape (when the word is shorter than k − 2). Then the automaton moves from left to right while changing states according to its transition function until it decides to rewrite the tape by deleting some symbols scanned by its window together with removing the cells of the tape containing the deleted symbols. Immediately after a rewrite the automaton "restarts" the computation on its shortened tape, that is, it enters its initial state and places the read/write window at the leftmost position again. A computation of an R-automaton ends when during scanning the tape it enters a halting state that can be either accepting, in which case it accepts the input word, or rejecting, in which case it rejects the input word.

The first fundamental result on restarting automata was a characterization of the class of deterministic context-free languages (DCFL) by a subclass of deterministic monotone R-automata. A computation of an R-automaton is monotone if the distances between the places of rewriting and the right sentinel are decreasing (maybe not strictly) during the whole computation. An R-automaton is monotone if all its computations are monotone.

An essential part of this paper is derived from [3] and [5]. We study the so-called RP-automata that slightly differ from R-automata in [3] and RW-automata in [4]. One restarting step by RW-automata is by RP-automata substituted by two consecutive steps: by a preparing step, and by a restarting step. With such a modification it is easier to present their so-called pumping properties.

The paper is structured as it follows. The next section introduces the model of RP-automata and its deterministic and monotone variant, and states some basic properties of the model. Section 3 introduces pumping instructions and pumping restarting automata. Pumping rewriting instructions correspond roughly to "pumping" used in the pumping lemma for context-free languages (cf. [2]) and pumping restarting automata are RP-automata that have only pumping rewriting instructions. We show there that using a strong cyclic form of deterministic RP-automata, we can check whether a given rewriting instruction is pumping by inspecting only computations on words of length limited by a constant. It follows new characterizations of DCFL by deterministic pumping restarting automata. Finally, we show conditions ensuring that a pumping instruction causes that an RP-automaton accepts a non-regular language.

A restarting automaton of type P, or an RP-automaton,

) is a device with a finite state control unit with the finite set of states Q containing two disjunctive subsets Q A , Q R of accepting and rejecting states, respectively. The automaton is equipped with a head moving on a finite linear flexible tape of items (cells). The first item of the tape contains always the left sentinel symbol | c, the last one the right sentinel symbol $, and each other item contains a symbol from a finite alphabet Σ (not containing | c, $). The head has a flexible read/write window of length at most k (for some k ≥ 1) -M scans k consecutive items or the rest of the tape when the distance to the right sentinel $ is less than k. We say that M is of window size k. In the initial configuration on an input word w ∈ Σ * , the tape contains the input word delimited by the sentinels | c and $, the control unit is in the initial state q 0 , and the window scans the left sentinel | c and the first k − 1 symbols of the input word (or the rest of the tape if the tape contents is shorter than k).

The computation of M is controlled by the transition function δ :

Here P(S) denotes the powerset of the set S, PC (k) is the set of possible contents of the read/write window of M, where for i, n ≥ 0

PC (i) .

The transition function represents a finite set of four different types of instructions (transition steps). Let q, q , q I be states from Q, u ∈ PC (k) , w ∈ PC ≤(k) , v ∈ PC ≤(k−1) and M be in state q with u be the contents of its read/write window:

(1) A move-right instruction of the form (q, u) → δ (q , MVR) is applicable if u = $. It causes M to enter the state q and to move its read/write head one item to the right.

(2) A preparing instruction (q, u) → δ (q I , PREPARE) changes M's state to a restarting state q I that determines the next instruction, which must be a restarting instruction.

(3) A restarting instruction I is of the form (q I , w) → δ RESTART(v), where |v| < |w| and if w contains any sentinel, v contains the corresponding sentinels, too. This instruction is applicable if w is a prefix of the contents of the read/write window. When executed, M replaces w with v (hereby it shortens its tape) and restarts -i.e. it enters the initial state and places the window at the leftmost position so that the first item in the window contains | c. Note that the pair (w, v) is unambiguously given by the state q I . We can assume that all pairs (w, v) such that |v| < |w| and the word w can be replaced with v by some RESTART instruction are ordered and that I is the index of (w, v) in that sequence. Thus, although RP-automaton is in general nondeterministic, each RESTART instruction of M corre-sponds unambiguously to one restart state q I . (4) A halting instruction of the form (q, u) → δ (q , HALT), where q ∈ Q A or q ∈ Q R , finishes the computation and causes M to accept or reject, respectively, the input word.

Thus, the set of states can be divided into three groupsthe halting states Q A ∪ Q R , the restarting states (involved at left-hand side of restarting instructions) and the rest, called the transition states.

A configuration of an RP-automaton M is a word αqβ , where q ∈ Q, and either α = λ and

here q represents the current state, αβ is the current contents of the tape, and it is understood that the read/write window contains the first k symbols of β or all symbols of β if |β | < k. An initial (restarting) configuration is of the form q 0 | cw$, where w ∈ Σ * . A rewriting configuration is of the form αq I β , where q I is a restarting state.

A computation of M is a sequence C = C 0 ,C 1 , . . . ,C j of configurations of M, where C 0 is a restarting configuration and C +1 is obtained from C by a step of M, for all , 0 ≤ < j, denoted as C M C +1 and * M is the reflexive and transitive closure of the single step relation M .

In general, an RP-automaton can be nondeterministic, i.e. there can be two or more instructions with the same left-hand side. If that is not the case, the automaton is deterministic. In what follows we are mostly interested in deterministic RP-automata, denoted det-RP.

An input word w is accepted by M if there is a computation that starts in the initial configuration with w (bounded by sentinels | c, $) on the tape and finishes in an accepting configuration where the control unit is in one of the accepting states. L(M) denotes the language consisting of all words accepted by M; we say that M accepts the language L(M).

Restarting steps divide any computation of an RPautomaton into certain phases that all start in the initial state in restarting configurations with the read/write window in the leftmost position. In a phase called cycle, the head moves to the right along the input list (with its read-/write window) until a restart occurs -in that case the computation is resumed in the initial configuration on a new, shorter, word. The phase from the last restart to the halting configuration is called tail. This immediately implies that any computation of any RP-automaton is finite (ending in a halting state).

The next proposition expresses certain lucidness of computations of deterministic RP-automata. The notation u ⇒ M v means that there exists a cycle of M starting in the initial configuration with the word u on its tape and finishing in the initial configuration with the word v on its tape; the relation ⇒ * M is the reflexive and transitive closure of ⇒ M .

The validity of the following proposition is obvious.

Proposition 1. (Correctness preserving property.) Let M be a deterministic RP-automaton and u ⇒ * M v for some words u, v. Then u ∈ L(M) iff v ∈ L(M).

By a monotone RP-automaton we mean an RPautomaton where the following holds for all computations: all items which appeared in the read/write window (and remained still on the tape) during one cycle will appear in the read/write window in the next cycle as well. It means, that during any computation of monotone RP-automaton the items from the read/write window of prepare configurations do not increase their distances from the right endmarker $.

Considering a deterministic RP-automaton M, it is for us convenient to suppose it to be in the strong cyclic form; it means that the words of length less than k, k being the length of its read/write window, are immediately (hence in the tail) accepted or rejected, and that M performs at least one cycle (at least one restarting) on any longer word.

We use the following obvious notation. RP denotes the class of all (nondeterministic) RP-automata. Prefix det-denotes the deterministic version, similarly mon-the monotone version. Prefix scf-denotes the version in the strong cyclic form. L (A), where A is some class of automata, denotes the class of languages accepted by automata from A. E.g., the class of languages accepted by deterministic monotone RP-automata is denoted by L (det-mon-RP).

Since all computations of RP-automata are finite, the following proposition is obvious. Rejected languages by det-RP-automata. Let M be a det-RP-automaton, and L(M) = L. We say that the language L (the complement of L) is rejected by M. We will often use the fact that the language and its complement can be recognized (distinguished) by the same det-RPautomaton.

The natural question of the decidability of monotonicity for a given RP-automaton is answered in the affirmative: Theorem 1. There is an algorithm which, given an RPautomaton M, decides whether M is monotone or not.

Proof: The proof is the same as the corresponding proof from [4]. The only difference between RW-and RP-automaton is that the RESTART operation of RWautomaton is unambiguously split into two consecutive instructions PREPARE and RESTART. This splitting has no influence on the decidability proof, since whenever the RESTART operation of RW-automaton is used/simulated in the original proof it can unambiguously be replaced by PREPARE and RESTART operation of RP-automaton.

In what follows, we consider only deterministic RPautomata. We write α ⇒ I β , for words α, β ∈ Σ * when α was shortened to β in one cycle consisting of several MVR steps followed by a PREPARE instruction and the restarting instruction I = (q I , w) → δ RESTART(v) with the restart state q I . Additionally, when | cxq I wy$ is the rewriting configuration corresponding to the reduction xwy ⇒ I xvy, for some words x, y, v, w, we will underline the occurrence of w rewritten in the cycle. That is, we will write xwy ⇒ I xvy. Analogously, α ⇒ * I β indicates a computation consisting of several such cycles that use the same restarting instruction I with the restarting state q I .

be a det-mon-RPautomaton, and ι = (q ι , w) → δ RESTART(v) a restarting instruction of M. We say that ι is a pumping instruction of M if w can be written as w = u 1 vu 2 , for some words u 1 , u 2 , u 1 = λ , and, for all x, y ∈ Σ * , xu 1 vu 2 y ⇒ ι xvy implies

We say that ι has pumping words u 1 , u 2 . If u 2 = λ we say that ι is a two-side pumping instruction. If u 2 = λ we say that ι is a one-side pumping instruction.

Note that a preparing instruction determines whether a given restarting instruction can be executed and each preparing instruction depends on move right instructions that are executed before it. Hence, the property of being a pumping instruction depends on the whole transition function of an RP-automaton.

Let M be a det-mon-RP-automaton and all restarting instructions of M are pumping instructions. Then we call M a pumping RP-automaton. We denote the property of pumping by the prefix pmp-.

be the RP-automaton with the set of states Q = {q 0 , q 1 , q A , q R }, the alphabet Σ = {a, b}, window size k = 2, the set of accepting states Q A = {q A }, the set of rejecting states Q R = {q R } and the transition function

The automaton has only one restarting instruction ι = δ (q 1 , ab) → δ RESTART(λ ). This instruction is two-side pumping instruction as w = ab can be written as u 1 vu 2 , where u 1 = a and u

cxy$ for some x, y ∈ {a, b} * , then it holds that xu j 1 vu j 2 y = xa j b j y ⇒ * ι xy = xvy, for all j ≥ 0, and xu j−1 1 u 1 vu 2 u j−1 2 y ⇒ ι xu j−1 1 vu j−1 2 y, for all j > 0. Evidently, the automaton M accepts the Dyck language of correctly paired parentheses, where a and b are the left and right parenthesis, respectively.

Note that M 1 is not in the strong cycling form.

Example 2. Consider the regular language L 2 of even length words over the alphabet {a}. This language can easily be accepted by the following RP-automaton

with the set of states Q = {q 0 , q 1 , q A , q R }, the alphabet Σ = {a}, window size k = 2, the set of accepting states Q A = {q A }, the set of rejecting states Q R = {q R } and the transition function

The automaton has only one restarting instruction ι = δ (q 1 , aa) → δ RESTART(λ ). At first glance this instruction seems to be pumping as it can be applied iteratively. The rewritten word w = aa can be written as u 1 vu 2 , where either u 1 = aa, v = λ , and u 2 = λ , or u 1 = a, v = λ , and u 2 = a. If u 1 = aa and xu 1 vu 2 y = xaay ⇒ ι xy = xvy for some x, y ∈ {a} * , then it does not hold xu j−1 1 u 1 vu 2 u j−1 2 y ⇒ ι xu j−1 1 vu j−1 2 y, for all j ≥ 1, as the deleting realized by the corresponding PREPARE and RESTART instructions is performed at the beginning of the word and not around v, for j > 1.

Similarly, when u 1 = a, v = λ , and u 2 = a, it can be shown that the condition xu j−1 1 u 1 vu 2 u j−1 2 y ⇒ ι xu j−1 1 vu j−1 2 y, for all j ≥ 1, does not hold. To obtain a pumping RP-automaton accepting the same language, we can change the automaton a bit so that it realizes the RESTART operation at the end of the word. For that we increase the window size to 3 and obtain RP-

with the set of states Q = {q 0 , q 1 , q A , q R }, the alphabet Σ = {a}, window size k = 3, the set of accepting states Q A = {q A }, the set of rejecting states Q R = {q R } and the transition function δ (q 0 , | c$) = {(q A , HALT)}, δ (q 0 , | ca$) = {(q R , HALT)}, δ (q 0 , aaa) = {(q 0 , MVR)}, δ (q 0 , aa$) = {(q 1 , PREPARE)}, δ (q 0 , | caa) = {(q 0 , MVR)}, δ (q 1 , aa) = {RESTART(λ )}. It is easy to see that the new automaton N 2 is pumping as it has single one-side pumping instruction that can be applied only at the right end of its tape.

Note that N 2 is in the strong cycling form.

The next lemma follows from the correctness preserving property.

be a detmon-RP-automaton of window size k, let p = |Q|, and ι = (q ι , w) → δ RESTART(v) be a restarting instruction of M. The instruction ι is a pumping instruction of M with pumping words u 1 , u 2 iff for all x, y ∈ Σ * such that xu 1 vu 2 y ⇒ ι xvy and each j,

Proof: Obviously, if ι is a pumping instruction then for all x, y ∈ Σ * such that xu 1 vu 2 y ⇒ ι xvy the condition (1) holds for each j ≥ 1.

To prove the opposite implication, let x, y be words such that xu 1 vu 2 y ⇒ ι xvy and for each j, 1 ≤ j ≤ p + k + 1 the condition (1) holds. We will show that the condition (1) is true also for any j > p + k + 1. Let w( j) = xu j 1 vu j 2 y, for all j ≥ 0. From (1) it follows that for each j, 1 ≤ j ≤ p+k +1, the computation on w( j) proceeds as follows:

where q j i denotes the state in which the i-th copy of u 1 is the prefix of the read/write window contents in the first cycle of the computation of M on w( j) and (q j j , u 1 vu 2 ω) → δ (q ι , PREPARE) is the preparing instruction followed by the instruction ι in the cycle. Further, let C j i denote the configuration of M corresponding to q j i during the first cycle on the word w( j).

Consider the first cycle of the computation of M on w( j), where j > p + k + 1. While the whole read/write window of M is inside the prefix xu p+k+1 1 of w( j), M executes the same instructions as in the first cycle on w(p + k + 1). Moreover, the contents of the read/write window of M is the same in all configurations C j i for all i,

Since M has p states, there are two positive integers r, d, 1 ≤ r < r + d ≤ p + 1 such that q j r = q j r+d and M executes from the configuration C j r+d the same sequence of instruction as between the configurations C j r and C j r+d (on w( j), where j ≥ r + 2d + k). Now, we can prove that (1) holds for any j ≥ 1. The base statement that the condition (1) holds for each j, 1 ≤ j ≤ p + k + 1 is trivially satisfied. Let us suppose that (1) holds for each j, 1 ≤ j ≤ n, where n ≥ p + k + 1. We will show that (1) holds also for j = n + 1. During the first cycle on w(n + 1), the automaton executes between the configurations C (n+1) r+d and C (n+1) n+1 on the word w(n+1) exactly the same sequence of instructions as between the configurations C (n+1−d) r and C (n+1−d) (n+1−d) on the word w(n + 1 − d). Therefore, it holds w(n + 1) = xu n 1 u 1 vu 2 u n 2 y ⇒ ι xu n 1 vu n 2 y and together with the assumption of the induction step, it holds xu j−1 1 u 1 vu 2 u j−1 2 y, for all j, 1 ≤ j ≤ n + 1. This completes the proof of the lemma.

Note that Lemma 1 could be used for testing, whether a given restarting instruction is pumping, if we were able to bound the length of x, y in it. As a corollary of the following proposition and lemma we get that it is the case. Proposition 3. For any deterministic RP-automaton M of window size k, there is a deterministic RP-automaton M of window size n, n ≥ k, such that M is in the strong cyclic form and L(M) = L(M ). In addition, when M is monotone then M is monotone as well, and when M is pumping then M is pumping as well, and if u ⇒ M v then u ⇒ M v.

Proof: An RP-automaton is in the strong cyclic form if it only accepts and rejects in tail computations words of bounded length. Thus, if the original RP-automaton was allowed to accept/reject in a tail computation on a word longer than the window size, we have to force it to perform one or more cycles so that in a tail computation it finally accepts (rejects) a word that together with the end-markers fits into the read/write window.

We can assume that M always accepts or rejects in a configuration in which it scans the right sentinel $. Otherwise, we can modify it so that instead of an "original" accepting (rejecting) state, it would enter a special state that causes moving to the right end and then accepting (rejecting). Since the language of words accepted (rejected) in a tail computation is regular, there are finite automata A and A C accepting these languages.

A new RP-automaton M will be of window size k = max{n A + 1, n C + 1, n M }, where n A , n C and n M are the numbers of states of A, A C and M, respectively. When moving right, the automaton M simultaneously simulates the computations of A, A C and M. The pumping lemma for regular languages implies that if M accepts or rejects w of length greater than k in a tail computation, then w ∈ L(A) or w ∈ L(A C ) and for some words x, y, z it holds:

The above modification ensures that when M accepts or rejects, it has already read the whole tape till the right sentinel. If M would accept or reject but M does not have also the left sentinel | c in its read/write window, the automaton M , instead of accepting/rejecting, deletes y by applying a suitable pair of preparing and restarting instruction of the form (q yz , yz$) → δ (q Iyz , PREPARE) and (q Iyz , y) → RESTART(λ ), for some new states q yz , q Iyz . Obviously, M is in strong cyclic form, L(M ) = L(M) and u ⇒ M v implies u ⇒ M v.

The described simulation preserves monotonicity and also pumping property, because all added restart operations are pumping and performed at the right end of the tape.

The next lemma enables extending Lemma 1 to detmon-RP-automata in the strong cyclic form.

be a detmon-RP-automaton with window size k, let p = |Q|, and let ι = (q ι , w) → δ RESTART(v) be a restarting instruction of M. There exists a constant m such that ι is a pumping instruction of M with pumping words u 1 , u 2 iff for all x, y ∈

Proof: Obviously, if ι is a pumping instruction then condition (2) is met for all words x, y such that xu 1 vu 2 y ⇒ ι xvy and for each j ≥ 1.

Let m = d + k + 1, where d denotes the number of possible pairwise different instructions of M. Evidently, 2) is satisfied also for any x, y ∈ Σ * of arbitrary length such that xu 1 vu 2 y ⇒ ι xvy. Then, by applying Lemma 1, we obtain that ι is a pumping instruction. The proof will be split into two claims. 1 u 1 vu 2 u j−1 2 y ⇒ ι xu j−1 1 vu j−1 2 y and also xu j−1 1 u 1 vu 2 u j−1 2 y y ⇒ ι xu j−1 1 vu j−1 2 y y , for all j, 1 ≤ j ≤ p + k + 1, as no symbol of y was visited in any of the corresponding cycles. Hence, the condition (2) holds when we do not restrict the length of y.

Claim 2. Assume that condition (2) holds for all words x, y, |x| ≤ m, y of arbitrary length, such that xu 1 vu 2 y ⇒ ι xvy. Then the condition (2) holds for all words x and y of arbitrary lengths, such that xu 1 vu 2 y ⇒ ι xvy.

Proof of claim: We will show that the condition (2) holds for arbitrary x by induction on the length of x.

Induction basis: For x of length at most m the condition (2) is true trivially.

Induction step: Let the claim be true for x of length at most n for some n ≥ m. We will show that the condition (2) is true also for x of length n + 1. Let x be a word of length n + 1.

In the first cycle of M on the word xu 1 vu 2 y, more than d MVR steps were performed while the read/write window was completely inside the word x. At least two of them were according to the same MVR instruction in a state q. Hence, we can write x = x 1 x 2 x 3 , for some words

where the prefix of length k of x 2 x 3 is the same as the prefix of length k of x 3 . That is, in both above configurations with the state q the automaton executes the same MVR instruction.

Therefore, when we leave out x 2 and the corresponding steps of the cycle, we obtain a valid cycle of M on the shorter word x 1 x 3 u 1 vu 2 y. Thus, it holds x 1 x 3 u 1 vu 2 y ⇒ ι x 1 x 3 vy and we can apply the assumption of the induction step that the condition (2) holds for words x of length at most n for the word x 1 x 3 to obtain that for each j, 1 ≤ j ≤ p + k + 1 :

Obviously, in each of the corresponding cycles we can insert back x 2 between x 1 and x 3 and the corresponding sequence of steps to obtain that

is true for all j, 1 ≤ j ≤ p + k + 1, which completes the proof of the claim.

By combining Claim 2 and Lemma 1, it follows that the instruction ι is pumping.

Corollary 1. Let M be a scf-det-mon-RP-automaton, and ι a restarting instruction of M. It is decidable whether ι is a pumping instruction or not.

The characterization of DCFL by R-automata was given in [3].

). DCFL = L (det-mon-R).

We show that DCFL can even be characterized by pmp-RP-automata. Proof: As the models of det-mon-R-and det-mon-RPautomata differ only slightly, we can use here a slightly modified proof of Lemma 8 in [3] stating that L (det-mon-R) ⊆ DCFL. For a given det-mon-RPautomaton M, a method from [3] can be used to construct a deterministic push-down automaton P that accepts the same language as M.

To show the opposite direction, we use the characterization of deterministic context-free languages by means of LR(1)-grammars in Greibach Normal Form and LR(1)analyzers (cf., e.g., [1]) 1 .

Proof: The inclusion follows from an analysis of the det-mon-R-automaton M simulating a syntactic analysis of a DCFL language L in [3]. Each det-mon-R-automaton M can be easily converted into a det-mon-RP-automaton M by splitting each restarting instruction of M into one preparing instruction and one restarting instruction of M . To see, that the resulting det-mon-RP-automaton M is 1 Recall that context-free grammar G = (N, T, P, S) is LR(k) for k ≥ 0 if for any string α exists unique partition α = β γu, where α, β , γ ∈ (N ∪ T ) * , u ∈ T * , such that there is a rightmost derivation S ⇒ * r β Au ⇒ r αβ u where A is a nonterminal. pumping we sketch the construction of M; the construction will also be helpful for better understanding of later results and proofs.

It is well known that if L is a deterministic context-free language and $ is a symbol not in the alphabet of L , then L • {$} is a deterministic prefix-free context-free language that can be parsed by a LR(0)-analyzer P 0 . This fact was used in [3]. Here, in order to construct a pmp-det-mon-RPautomaton, we use a similar construction of an LR(1)analyzer P of L that is based on an LR(1)-grammar in Greibach Normal Form. The existence of such analyzer for any DCFL is proved in [1].

Based on the simulation of P on a word w we can construct the derivation tree T w (the inner vertices of which are labeled with nonterminals and leaves correspond to terminal symbols). Thus, for any word w ∈ L there is exactly one derivation tree T w . The standard pumping lemma for context-free languages implies existence of two constants p, q > 0 such that for any word w with length greater than p there are (complete) subtrees T 1 and T 2 of T w such that T 2 is a subtree of T 1 and roots of both subtrees have the same label (cf. Fig. 1); in addition, T 2 has fewer leaves than T 1 , T 1 has at most q leaves and |u 1 | > 0. The word u 1 is nonempty, because the right-hand side of the rule used to rewrite the nonterminal A in the root of T 1 must start with a terminal (the grammar is in Greibach Normal form).

Obviously, replacing T 1 with T 2 , we get the derivation tree T w(0) for a shorter word w(0) (if w = xu 1 vu 2 y then w(0) = xvy). Analogously, replacing T 2 with T 1 , we get the derivation tree T w(2) for a longer word w(2) where w(2) = xu 2 1 vu 2 2 y. If we repeat this replacing of T 2 with T 1 i-times we obtain the derivation tree T w(i+1) for a word w(i + 1) where w(i + 1) = xu i+1 1 vu i+1 2 y. The key to a construction of the det-mon-R-automaton M in [3] is the possibility to identify the leftmost subword u 1 vu 2 corresponding to subtrees T 1 and T 2 as shown in Fig. 1 reading from left to right with the help of constant size memory only. In its constant size memory M stores all maximal subtrees of the derivation tree with all their leaves in the buffer. When it identifies a subtree like T 1 above, M performs the corresponding deleting by a RESTART operation. Obviously, the read/write window of length k > q is sufficient for that.

If that is not the case then M forgets the leftmost of these subtrees with all its n ≥ 1 leaves, and reads n new symbols to the right end of the buffer (performing MVRinstructions). Then M continues constructing the maximal subtrees with all leaves in the (updated) buffer (simulating P). Short words of length less than k are accepted/rejected in tail computations.

To obtain M it is sufficient to use instead of restarting instructions of M the corresponding preparing and restarting instructions of RP-automaton. The preparing and restarting instructions can handle LR(1)-analysis in the same way as M the LR(0)-analysis. The resulting RPautomaton M preserves the determinism and monotonicity of M; from the construction it is clear that M is pumping as well.

Note. While the previous proof is based on the paper [3], a similar proof can be based on the constructions from paper [7] based on deterministic list automata.

The following corollary is a consequence of the previous theorem and Proposition 3.

In what follows, we will write pmsc-instead of pmp-scf-. In what follows, we aim to obtain some conditions for a det-RP-automaton to accept a non-regular language. At first, we conjecture, that each pmp-det-mon-RPautomaton that does not have any two-side pumping instruction generates a regular language. On the other hand, a pmp-det-mon-RP-automaton having a two-side pumping instruction can still accept a regular language. This can be seen in the following example.