We introduce a new type of the deterministic monotone restarting automaton that enables new types of characterization of the class of deterministic context-free languages (DCFL) based on pumping. The characterization is obtained through new types of normalizations of deterministic monotone restarting automata. This paper is the first step to prepare notions for studying the relation between restarting automata and analog neuron automata, and for studying degrees of non-regularity of DCFL.
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 cj 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 cj 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. 2
A restarting automaton of type P, or an RP-automaton, M = (Q; S; cj; $; q0; k; d ; QA; QR) (with k-bounded lookahead) is a device with a finite state control unit with the finite set of states Q containing two disjunctive subsets QA, QR 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 cj, the last one the right sentinel symbol $, and each other item contains a symbol from a finite alphabet S (not containing cj, $). 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 2 S , the tape contains the input word delimited by the sentinels cj and $, the control unit is in the initial state q0, and the window scans the left sentinel cj 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 d : (Q n (QA [ QR))
PC (k) !
P(Q fMVR; PREPAREg) [ fRESTART(v) j v 2 PC (k 1)g:
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) := (f cjg Si 1) [ Si [ (S i 1 f$g) [ (f cjg S i 2 f$g); n k S n := S Si and PC (k) := S PC (i):
i=0 i=0
The transition function represents a finite set of four different types of instructions (transition steps). Let q; q0; qI be states from Q, u 2 PC (k), w 2 PC (k), v 2 PC (k 1) and M be in state q with u be the contents of its read/write window:
(
(
(
(
Thus, the set of states can be divided into three groups – the halting states QA [ QR, 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 aqb , where q 2 Q, and either a = l and b 2 f cjg S f$g or a 2 f cjg S and b 2 S f$g; here q represents the current state, ab is the current contents of the tape, and it is understood that the read/write window contains the first k symbols of b or all symbols of b if jb j < k. An initial (restarting) configuration is of the form q0 cjw$, where w 2 S . A rewriting configuration is of the form aqI b , where qI is a restarting state.
A computation of M is a sequence C = C0;C1; : : : ;C j of configurations of M, where C0 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 cj, $) 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.
M be a deterministic RP-automaton and u )M v for some words u, v. Then u 2 L(M) iff v 2 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.
Proposition 2. The classes L (det-mon-RP) and L (det-RP) are closed under complement.
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 a )I b , for words a; b 2 S when a was shortened to b in one cycle consisting of several MVR steps followed by a PREPARE instruction and the restarting instruction I = (qI ; w) !d RESTART(v) with the restart state qI . Additionally, when cjxqI 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, a )I b indicates a computation consisting of several such cycles that use the same restarting instruction I with the restarting state qI . 3
Let M = (Q; S; cj; $; q0; k; d ; QA; QR) be a det-mon-RPautomaton, and i = (qi ; w) !d RESTART(v) a restarting instruction of M. We say that i is a pumping instruction of M if w can be written as w = u1vu2, for some words u1; u2, u1 6= l , and, for all x; y 2 S , xu1vu2y )i xvy implies xu1j 1u1vu2u2j 1y )i xu1j 1vu2j 1y, for all j 1: We say that i has pumping words u1; u2. If u2 6= l we say that i is a two-side pumping instruction. If u2 = l we say that i 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-.
Example 1. Let M1 = (Q; S; cj; $; q0; k; d ; QA; QR) be the RP-automaton with the set of states Q = fq0; q1; qA; qRg, the alphabet S = fa; bg, window size k = 2, the set of accepting states QA = fqAg, the set of rejecting states QR = fqRg and the transition function d (q0; cj$) = f(qA; HALT)g; d (q0; bb) = f(q0; MVR)g; d (q0; cja) = f(q0; MVR)g; d (q0; ab) = f(q1; PREPARE)g; d (q0; cjb) = f(q0; MVR)g; d (q1; ab) = fRESTART(l )g; d (q0; aa) = f(q0; MVR)g; d (q0; a$) = f(qR; HALT)g; d (q0; ba) = f(q0; MVR)g; d (q0; b$) = f(qR; HALT)g:
The automaton has only one restarting instruction i = d (q1; ab) !d RESTART(l ). This instruction is two-side pumping instruction as w = ab can be written as u1vu2, where u1 = a and u2 = b are nonempty, v = l . If q0 cjxu1vu2y$ = q0 cjxaby$ ` cjxq1u1vu2y$ `i q0 cjxvy$ = q0 cjxy$ for some x; y 2 fa; bg , then it holds that xu1j vu2j y = xa jb jy )i xy = xvy, for all j 0, and xu1j 1u1vu2u2j 1y )i xu1j 1vu2j 1y, 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 M1 is not in the strong cycling form.
Example 2. Consider the regular language L2 of even length words over the alphabet fag. This language can easily be accepted by the following RP-automaton M2, M2 = (Q; S; cj; $; q0; k; d ; QA; QR) with the set of states Q = fq0; q1; qA; qRg, the alphabet S = f g a , window size k = 2, the set of accepting states QA = fqAg, the set of rejecting states QR = fqRg and the transition function d (q0; cj$) = f(qA; HALT)g; d (q0; aa) = f(q1; PREPARE)g; d (q0; cja) = f(q0; MVR)g; d (q1; aa) = fRESTART(l )g; d (q0; a$) = f(qR; HALT)g: The automaton has only one restarting instruction i = d (q1; aa) !d RESTART(l ). At first glance this instruction seems to be pumping as it can be applied iteratively. The rewritten word w = aa can be written as u1vu2, where either u1 = aa, v = l , and u2 = l , or u1 = a, v = l , and u2 = a. If u1 = aa and xu1vu2y = xaay )i xy = xvy for some x; y 2 fag , then it does not hold xu1j 1u1vu2u2j 1y )i xu1j 1vu2j 1y, 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 u1 = a, v = l , and u2 = a, it can be shown that the condition xu1j 1u1vu2u2j 1y )i xu1j 1vu2j 1y, 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 RPautomaton N2 = (Q; S; cj; $; q0; k; d ; QA; QR) with the set of states Q = fq0; q1; qA; qRg, the alphabet S = fag, window size k = 3, the set of accepting states QA = fqAg, the set of rejecting states QR = fqRg and the transition function d (q0; cj$) = f(qA; HALT)g; d (q0; cja$) = f(qR; HALT)g; d (q0; aaa) = f(q0; MVR)g; d (q0; aa$) =f(q1; PREPARE)g; d (q0; cjaa) = f(q0; MVR)g; d (q1; aa) = fRESTART(l )g: It is easy to see that the new automaton N2 is pumping as it has single one-side pumping instruction that can be applied only at the right end of its tape.
Note that N2 is in the strong cycling form.
The next lemma follows from the correctness preserving property.
Lemma 1. Let M = (Q; S; cj; $; q0; k; d ; QA; QR) be a
detmon-RP-automaton of window size k, let p = jQj, and
i = (qi ; w) !d RESTART(v) be a restarting instruction
of M. The instruction i is a pumping instruction of M
with pumping words u1; u2 iff for all x; y 2 S such that
xu1vu2y )i xvy and each j, 1 j p + k + 1 it holds that
xu1j 1u1vu2u2j 1y )i xu1j 1vu2j 1y:
(
Proof: Obviously, if i is a pumping instruction then for
all x; y 2 S such that xu1vu2y )i xvy the condition (
To prove the opposite implication, let x; y be words such
that xu1vu2y )i xvy and for each j, 1 j p + k + 1 the
condition (
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 xu1p+k+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 ji for all i, 1 i p + 1, because juk1j k. Since M has p states, there are two positive integers r; d, 1 r < r + d p + 1 such that q jr = q jr+d and M executes from the configuration C jr+d the same sequence of instruction as between the configurations C jr and C jr+d (on w( j), where j r + 2d + k).
Now, we can prove that (
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 M0 of window size n, n k, such that M0 is in the strong cyclic form and L(M) = L(M0). In addition, when M is monotone then M0 is monotone as well, and when M is pumping then M0 is pumping as well, and if u )M v then u )M0 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 AC accepting these languages.
A new RP-automaton M0 will be of window size k0 = maxfnA + 1; nC + 1; nMg, where nA, nC and nM are the numbers of states of A, AC and M, respectively. When moving right, the automaton M0 simultaneously simulates the computations of A, AC and M. The pumping lemma for regular languages implies that if M accepts or rejects w of length greater than k0 in a tail computation, then w 2 L(A) or w 2 L(AC) and for some words x; y; z it holds: w = xyz, jyzj < k0, jyj > 0 and xz 2 L(A) or xz 2 L(AC).
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 M0 does not have also the left sentinel cj in its read/write window, the automaton M0, instead of accepting/rejecting, deletes y by applying a suitable pair of preparing and restarting instruction of the form (qyz; yz$) !d (qIyz; PREPARE) and (qIyz; y) ! RESTART(l ), for some new states qyz; qIyz. Obviously, M0 is in strong cyclic form, L(M0) = L(M) and u )M v implies u )M0 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.
Lemma 2. Let M = (Q; S; cj; $; q0; k; d ; QA; QR) be a
detmon-RP-automaton with window size k, let p = jQj, and
let i = (qi ; w) !d RESTART(v) be a restarting instruction
of M. There exists a constant m such that i is a pumping
instruction of M with pumping words u1; u2 iff for all x; y 2
S satisfying jxj m, jyj < k, xu1vu2y )i xvy it holds
for each j; 1 j p + k + 1 :
xu1j 1u1vu2u2j 1y )i xu1j 1vu2j 1y:
(
Proof: Obviously, if i is a pumping instruction then
condition (
Let m = d + k + 1, where d denotes the number of
possible pairwise different instructions of M. Evidently,
d = p jPC (k)j p (jSj + 3)k. We will show that if
condition (
Proof of claim: According to the assumptions of the
claim, for y of length at most k 1 the condition (
Claim 2. Assume that condition (
Proof of claim: We will show that the condition (
Induction basis: For x of length at most m the condition
(
Induction step: Let the claim be true for x of length at
most n for some n m. We will show that the condition
(
In the first cycle of M on the word xu1vu2y, 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 = x1x2x3, for some words x1; x2; x3 such that jx2j > 0, jx3j k and q0 cjx1x2x3u1vu2y$ `M `M `M `M cjx1qx2x3u1vu2y$ cjx1x2qx3u1vu2y$ cjx1x2x3qi u1vu2y$ q0 cjx1x2x3vy$; where the prefix of length k of x2x3 is the same as the prefix of length k of x3. That is, in both above configurations with the state q the automaton executes the same MVR instruction.
Therefore, when we leave out x2 and the corresponding
steps of the cycle, we obtain a valid cycle of M on the
shorter word x1x3u1vu2y. Thus, it holds x1x3u1vu2y )i
x1x3vy and we can apply the assumption of the induction
step that the condition (
j p + k + 1, which completes the
Obviously, in each of the corresponding cycles we can insert back x2 between x1 and x3 and the corresponding sequence of steps to obtain that x1x2x3u1j 1u1vu2u2j 1
y )i x1x2x3u1j 1vu2j 1y
By combining Claim 2 and Lemma 1, it follows that the instruction i is pumping.
Corollary 1. Let M be a scf-det-mon-RP-automaton, and i a restarting instruction of M. It is decidable whether i is a pumping instruction or not.
The characterization of DCFL by R-automata was given in [3].
Theorem 2 ([3]). DCFL = L (det-mon-R).
We show that DCFL can even be characterized by pmp-RP-automata.
Theorem 3. DCFL = L (pmp-RP) = L (det-mon-RP)
Proof: The theorem is a consequence of the following two lemmas.
Lemma 3. L (det-mon-RP)
DCFL.
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(
L (pmp-RP).
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 M0 by splitting each restarting instruction of M into one preparing instruction and one restarting instruction of M0. To see, that the resulting det-mon-RP-automaton M0 is 1Recall that context-free grammar G = (N; T; P; S) is LR(k) for k 0 if for any string a exists unique partition a = b gu, where a; b ; g 2 (N [ T ) , u 2 T , such that there is a rightmost derivation S )r b Au )r ab u where A is a nonterminal. x u1 T2 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 L0 is a deterministic context-free
language and $ is a symbol not in the alphabet of L0, then
L0 f$g is a deterministic prefix-free context-free language
that can be parsed by a LR(0)-analyzer P0. This fact was
used in [3]. Here, in order to construct a
pmp-det-mon-RPautomaton, we use a similar construction of an
LR(
Based on the simulation of P on a word w we can construct the derivation tree Tw (the inner vertices of which are labeled with nonterminals and leaves correspond to terminal symbols). Thus, for any word w 2 L there is exactly one derivation tree Tw. 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 T1 and T2 of Tw such that T2 is a subtree of T1 and roots of both subtrees have the same label (cf. Fig. 1); in addition, T2 has fewer leaves than T1, T1 has at most q leaves and ju1j > 0. The word u1 is nonempty, because the right-hand side of the rule used to rewrite the nonterminal A in the root of T1 must start with a terminal (the grammar is in Greibach Normal form).
Obviously, replacing T1 with T2, we get the derivation
tree Tw(0) for a shorter word w(0) (if w = xu1vu2y then
w(0) = xvy). Analogously, replacing T2 with T1, we get the
derivation tree Tw(
The key to a construction of the det-mon-R-automaton M in [3] is the possibility to identify the leftmost subword u1vu2 corresponding to subtrees T1 and T2 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 T1 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 M0 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(
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.
Notation. In what follows, we will write pmsc- instead of pmp-scf-.
DCFL = L (pmsc-RP) = L (scf-det-mon-RP):
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.
Example 3. Let M3 = (Q; S; cj; $; q0; k; d ; QA; QR) be the RP-automaton with the set of states Q = fq0; q1; qa; qb; qAg, the alphabet S = fa; bg, window size k = 2, the set of accepting states QA = fqAg, the set of rejecting states QR = 0/ and the transition function d (q0; cj$) = f(qA; HALT)g; d (q0; bb) = f(q0; MVR)g; d (q0; cja) = f(q0; MVR)g; d (q0; ab) = f(q1; PREPARE)g; d (q0; cjb) = f(q0; MVR)g; d (q1; ab) = fRESTART(l )g; d (q0; aa) = f(q0; MVR)g; d (q0; a$) = f(qa; PREPARE)g; d (q0; ba) = f(q0; MVR)g; d (q0; b$) = f(qb; PREPARE)g d (qa; a) = fRESTART(l )g; d (qb; b) = fRESTART(l )g:
The automaton differs from the automaton M1 of Example 1 only slightly. It has two new restarting states qa and qb that enable to delete any symbol to the left from the right sentinel $. Nevertheless, the first restarting instruction i = (q1; ab) !d RESTART(l ) is still two-side pumping instruction (see Example 1). The automaton M3 is deterministic and monotone. In contrast to M1, it is in the strong cyclic form and accepts all words over the alphabet fa; bg.
Hence, we define a property of two-side pumping instructions which ensures that the resulting det-mon-RPautomaton does accept a non-regular language.
Definition 4. Let M = (Q; S; cj; $; q0; k; d ; QA; QR) be a pmp-RP-automaton accepting the language L = L(M). Let i = (qr; u1vu2) !d RESTART(v) be a two-side pumping restarting instruction of M with pumping words (strings) u1; u2 and xu1vu2y )i xvy, for some x; y 2 S .
Let p be a positive integer. We say that i is a (p; x; y)distinguishing instruction for M if at least one of the following cases occurs:
(I) xu1mvu2my 2 L, and xu1mvu2mu2p jy 2= L, for all j 1, m 0,
(II) xu1mvu2my 2 L, and xu1p ju1mvu2my 2= L, for all j 1, m 0,
(III) xu1mvu2my 2= L, and xu1mvu2mu2p jy 2 L, for all j 1, m 0,
(IV) xu1mvu2my 2= L, and xu1p ju1mvu2my 2 L, for all j 1, m 0.
We say that i is a distinguishing instruction for M if there are p; x; y such that i is a (p; x; y)-distinguishing instruction for M.
We say that M is a distinguishing RP-automaton if there is a distinguishing instruction i for M. We write dist-RPautomaton to denote a distinguishing pmp-RP-automaton. Example 4. Let us consider the automaton M1 = (Q; S; cj; $; q0; k; d ; QA; QR) from Example 1. We will show that M1 is a dist-RP-automaton. The automaton has only one restarting instruction i = (q1; ab) !d RESTART(l ). This instruction is a two-side pumping instruction with pumping strings u1 = a and u2 = b and ab = xu1vu2y )1 xvy = l , for x = l , v = l , y = l . The instruction i is a (p; x; y)-distinguishing instruction for M1 for p = 1. Namely, for all j 1; m 0 it holds and also xu1mvu2my = ambm 2 L(M1) and xu1mvu2mu2p jy = ambmb j 2= L(M1); xu1mvu2my = ambm 2 L(M1) and xu1mu1p jvu2my = ama jbm 2= L(M1): Theorem 4. Let L = L(M) 6= 0/ be a deterministic contextfree language accepted by a dist-RP-automaton M. Then L is a non-regular language.
Proof. To obtain a contradiction, we suppose that M = (Q; S; cj; $; q0; k; d ; QA; QR) is a dist-RP-automaton accepting a regular language L = L(M). Since M is a dist-RPautomaton, it has a (p; x; y)-distinguishing instruction i = (qi ; u1vu2) !d RESTART(v), for some x; y; v 2 S , u1; u2 2 S+; qi 2 Q and p 1. As L is regular, there exists a deterministic finite automaton A with nA states accepting the language L(A) = L.
The proof follows by the analysis of the four possible cases of (p; x; y)-distinguishing property of i: Case (I): From the definition, for all m 0, j 1 it holds xu1mvu2my 2 L and xu1mvu2mu2p jy 2= L. Let qm j denote the state of the automaton A in which it reads the first symbol of the j-th copy of u2 to the right from v. That is, A is in the state qm j after reading xu1mvu2j 1, for j 1. For m > nA, there exist integers r; s, 1 r < s nA + 1 such that qmr = qms . Then, for all i 0, it holds qmr = qmr+i (r s) and the automaton A accepts all words of the form xu1mvu2m+i (s r)y. For i = p, we obtain that xu1mvu2m+p (s r)y 2 L which contradicts the assumption xu1mvu2mu2p jy 2= L, for j = (s r). Case (II): From the definition, for all m 0, j 1 it holds xu1mvu2my 2 L, and xu1p jumvu2my 2= L. Let qm j denote the 1 state of the automaton A in which it reads the first symbol of the j-th copy of u1 to the right from x. That is, A is in the state qm j after reading xu1j 1, for j 1. For m > nA, there exist integers r; s, 1 r < s nA + 1 such that qmr = qms . Then, for all i 0, it holds qmr = qmr+i (r s) and the automaton A accepts all words of the form xu1m+i (s r)vu2my. For i = p, we obtain that xu1m+p (s r)vu2my 2 L which contradicts the assumption xu1p ju1mvu2my 2= L, for j = (s r).
Analysis of conditions (III) and (IV) from Definition 4 is analogous to the shown cases.
As each dist-RP-automaton is deterministic and monotone (Definition 4), it accepts a deterministic context-free language (Lemma 3). Hence, Lemma 3, Theorem 4 and Proposition 3 imply the following corollary ( denotes the proper subset relation).
Corollary 3. L (dist-RP) = L (scf-dist-RP) DCFL.
Remark. We conjecture that L (scf-dist-RP) is equal to the set of all non-regular DCFL. But it remains an open problem. 4
We plan in the near future to show that any pmsc-RPautomaton M which accepts a non-regular language can be transformed in a scf-dist-RP-automaton, for which all its two-side pumping instructions are distinguishing. Let us denote such type of automata as strongly distinguishing RP-automata (sdist-RP-automata). The sdist-RP-automata will allow to extend the results from [8] achieved by deterministic context-free grammars. Further, it will allow to introduce some types of degrees of non-regularity of DCFL, e.g., according to the number of distinguishing instructions in a strongly distinguishing RP-automaton. The combinations of this measure with other measures typical for restarting automata (e.g., the length of rewriting windows) will give us natural measures for complexity of DCFL.
Finally, sdist-RP-automata will create a nice tool for localization and measures for syntactic errors in deterministic context-free languages.
We thank the anonymous referees whose comments and suggestions have helped to improve the presentation of this paper.