This paper follows the paper [6], where we have studied restarting automata recognizing deterministic contextfree languages (DCFL) with a particular type of pumping patterns. This type of pumping patterns ensures the nonregularity of the recognized languages.

In this paper, we are looking for two types of pumping patterns. The first type of pumping patterns should ensure the non-regularity of the languages recognized by a certain type of restarting automata. In contrast, the second type of pumping patterns should ensure the regularity of the languages recognized by this type of restarting automata. The union of both of these types of pumping patterns should cover all possible pumping patterns defined by the mentioned type of restarting automata.

Any deterministic context-free language L can be accepted by a LR(1)-analyzer (using lookahead of size 1), but the language L • {$}, where $ is a special end-marker not in the alphabet of L) can be accepted by a LR(0)analyzer [3]. In [4], it was shown that any deterministic context-free language can be accepted by a deterministic monotone restarting automaton. This was proved by simulating any given LR(0)-analyzer by a deterministic monotone restarting automaton. Hence, the computations of such automata were controlled by LR(0)grammars. Therefore, in what follows, we will use constructions based on properties of phrase structures generated by LR(0)-grammars and we will study pumping patterns based on LR(0)-grammars.

This paper should serve as a step to refine the concepts from [5], where it was shown that restarting automata can serve as a formal model for functional generative description (FGD) of a natural language. Functional generative description is a dependency-based descriptive system that has been developed since the 1960's, see esp. [7]. FGD was originally implemented as a generative procedure, but later its authors have been interested in a more declarative representation. The subject of the paper [5] concerns the foundations of a reduction system using a complex restarting automaton. The reduction system is more complex than a reduction system for a (shallow) syntactic analyzer since it provides not only the possibility of checking the well-formedness of the (surface) analysis of a sentence, but also its meaning -tectogrammatical representation in terms of FGD. Such a reduction system makes it possible to define the analysis as well as the synthesis of a sentence formally.

A descriptive system [5] DS of a natural language L should determine: Let us note that LM is an artificial (formal) unambiguous language, which can be described by a restarting auto-maton controlled by an LR(0)-grammar. An important feature modeled by LM is valency. More about valency can be found in [1]. There are types of valency features that can be modeled as pumping patterns of non-regular type (e.g., obligatory adjuncts), and there are other valency features that can be modeled as pumping patterns of regular type (e.g., optional adjuncts).

Another recent motivation for this paper comes from a completely different area. The last results of this paper should support the analysis of analog neuron hierarchy of binary-state neural networks (NNs) with an increasing number of extra analog-state neurons, which has been introduced in [8] for studying the power of NNs with realistic weights between integers and rational numbers with respect to the Chomsky hierarchy.

Note that the problem of the regularity of deterministic context-free languages gained attention already in the 60s. Algorithms deciding whether a given deterministic pushdown automaton accepts a regular language were proposed by Stearns [9] and Valiant [10].

This paper is structured as follows. The next section contains basic notions and basic properties of LR(0)grammars. Section 3 introduces the concepts of our interest and presents the first main result. Section 4 presents the results about total separations. The paper concludes with a summary of future work to be done to fulfill all our plans.

We suppose that the reader is familiar with the basics of formal language and automata theory presented, e.g., in [3]. For technical reasons, we give a list of some notions and definitions related to formal grammars. Context-free grammars. A context-free grammar G is defined by a 4-tuple G = (V, Σ, R, S) where Σ ⊂ V , N = V \ Σ, and N, Σ are finite sets of nonterminal and terminal symbols, respectively, R ⊂ N × V * is a finite relation of rewrite (production) rules, and S ∈ N is the start symbol.

The grammar G generates the context-free language

R w}. We write u ⇒ ≤p v for some non-negative integer p if u ⇒ * v and v is derived from u by at most p derivation steps (⇒). A similar meaning has the denotation u ⇒ ≤p R v. In what follows, we will primarily work with the rightmost derivations and write ⇒ instead of ⇒ R .

Any non-empty context-free language L = L(G) = / 0 can be generated by a reduced context-free grammar G that excludes unreachable and unproductive symbols, that is, for every A ∈ N, there exist α, β ∈ V * such that S ⇒ * αAβ , and for every A ∈ N there is w ∈ Σ * such that A ⇒ * w, respectively. In the following, we work with reduced context-free grammars only.

We say that a context-free grammar G = (V, Σ, R, S) is linear if the right-hand side of any rule from R contains at most one variable (nonterminal).

For any non-empty word a 1 • • • a n , with a 1 , . . . , a n ∈ Σ, the derivation S ⇒ * a 1 • • • a n can be described by a derivation tree which is an ordered tree satisfying:

1. Inner vertices are labeled with nonterminals.

2. The root is labeled with the start symbol S.

A together with the subtrees rooted in its children form a complete branch of the tree.

4. The leaves in the tree are labeled (from left to right) with the terminal symbols a 1 , . . . , a n ∈ Σ.

Removing condition 2 we get the definition of a (computation) derivation sub-tree.

A grammar G is unambiguous if every non-empty string w ∈ L(G) has a unique derivation tree, or equivalently a unique rightmost derivation.

The results of our paper heavily depend on the characterization of the class of deterministic context-free languages by LR(0)-grammars and corresponding parsers. Following [3], we, therefore, give the necessary definitions and the most relevant results.

). Let G = (V, Σ, R, S) be a reduced contextfree grammar. Then G is unambiguous if and only if every α ∈ V * , such that S ⇒ * R α, has exactly one handle except S, which has none.

In general, the identification of a handle in a string is not uniquely defined, which is not true for LR(0) grammars. Definition 2. Let G = (V, Σ, R, S) be a reduced contextfree grammar such that S ⇒ + R S is not possible in G. We say G is an LR(0)-grammar if, for each w, w ,

Note that as a consequence of the above definition we have that A = A , β = β , α = α , γ = αβ = α β and x = w . Thus, if G is an LR(0)-grammar, then the rightmost derivation of the word w by G and the left-right analysis is unique (deterministic). In this paper, we consider LR(0) grammars rather as analytical grammars. A language generated by an LR(0)-grammar is called LR(0)-language.

Theorem 1 (LR(0)-language characterization theorem from [3]). Let L ⊆ Σ * . The following four statements are equivalent.

(a) L is an LR(0) language.

(b) L is a deterministic context-free language and for all

x ∈ Σ + , w, y ∈ Σ * , if w ∈ L, wx ∈ L, and y ∈ L, then yx ∈ L.

(c) There exists a deterministic pushdown automaton A with a single final state q f and a pushdown symbol Z f such that each word w ∈ L is accepted by A by entering the state q f with Z f as the only symbol in its pushdown.

(d) There exist strict deterministic languages L 0 and L 1 such that L = L 0 L * 1 . Note that strict deterministic languages are deterministic context-free languages recognizable by empty pushdown, or equivalently prefix-free deterministic contextfree languages.

Let us recall semi-Dyck languages. Let r ≥ 1, Σ r = {a 1 , . . . , a r }, Σr = { ā1 , . . . , ār } and Σ = Σ r ∪ Σr . The semi-Dyck language D r is the language generated by the grammar G r = (V r , Σ, P, S), where V r = Σ ∪ {S}, and R contains the following production rules:

Informally, D r is the set of all well-balanced parentheses containing r different pairs of brackets [3]. The semi-Dyck languages are examples of context-free languages that are not linear context-free languages. Additionally, they can be used to separate LR(0)-languages from the strict deterministic languages.

). Let D r ⊂ Σ * be the semi-Dyck language for some r ≥ 1. Then D r is an LR(0)-language, but not a strict deterministic language. LR(0)-analyzer. If L is generated by an LR(0)grammar G, then there exists an LR(0)-analyzer P(G) for L with the following important properties (see [3]):

(a) For each word w ∈ L, there is exactly one rightmost derivation of w in G, which corresponds to the LR(0)analysis of the word w by P(G).

(b) Let u be a prefix of the content of the input tape w = uv, which has already been read by a computation of P(G). Then there exists a suffix v such that uv ∈ L iff P(G) did not halt and not reject while reading u.

Let L ⊆ Σ * be a deterministic context-free language (DCFL), and $ / ∈ Σ. Then, according to [3], there are LR(0)-grammar G(0, $) generating the language L • {$}, and a corresponding LR(0)-analyzer P(G(0, $)) of L • {$}; P(G(0, $)) is a deterministic push-down automaton with $ as the rightmost symbol on its input-tape.

To stress its property, we will sometimes write LR(0,$)grammar instead of grammar G(0, $). We denote the set of LR(0)-grammars by LRG and the set of LR(0,$)-grammars by LRG($). Linear LRG. We say that a context-free grammar G is linear if the right-hand side of any rule from G contains at most one variable (nonterminal). We also consider linear LR(0)-grammars. We denote the linearity by the prefix lin-, and the class of linear LR(0)-grammars as lin-LRG.

In what follows, L (A), where A is some class of grammars, denotes the class of languages generated by grammars from A. E.g., the class of languages generated by linear LR(0)-grammars is denoted by L (lin-LRG).

The first goal of our paper is to specify properties of deterministic (linear) context-free grammars that assure that the corresponding (linear) language is non-regular. In this section, we show such properties. We start with several definitions and notations. Pumping notions. Let G = (V, Σ, R, S) be an LR(0)grammar generating (analyzing) the language L = L(G), and P(G) be the corresponding LR(0)-analyzer for G. Let w ∈ L(G), w = xu 1 vu 2 y, where x, u 1 , v, u 2 , y ∈ Σ * , u 1 u 2 ∈ Σ + are given by the derivation tree T w from Fig. 1. The proper sub-trees T 1 and T 2 of T w are (computation) subtrees whose roots are labeled with the same nonterminal A, thus by replacing T 1 with T 2 properly inside of T w , we again get a derivation tree, namely the derivation tree T w(0) for the word w(0) = xvy ∈ L(G).

Analogously, replacing T 2 with a copy of T 1 , we get the derivation tree T w(2) for a longer word w(2) = xu 2 1 vu 2 2 y. If we repeat i times such replacing of T 2 with T 1 we obtain the derivation tree T w(i+1) for the word w(i+1) = xu i+1 1 vu i+1 2 y. Pumping tree, prefix, infix, pattern and reduction. Let x, u 1 , v, u 2 , A, y, T 1 be as on Fig. 1. Then we say that P p = xu 1 vu 2 is an (x, u 1 , A, v, u 2 )-pumping prefix by G, P in = xu 1 vu 2 y is an (x, u 1 , A, v, u 2 , y)-pumping infix by G, and that T 1 is a pumping tree of P p . Recall that the LR(0)analysis by P(G) of the prefix P p in any word of the form P p γ is the same, for any γ ∈ Σ * . We say that (u 1 , A, v, u 2 ) is a pumping pattern by G (of P p ). Let us recall that for any z ∈ Σ * , the LR(0)-analyzer P(G)) reduces xu 1 vu 2 z into xvz. We write xu 1 vu 2 z ⇐ P(G) xvz, and say that xu 1 vu 2 z ⇐ P(G)

The structure of a derivation tree.

xvz is an (x, u 1 , A, v, u 2 )-pumping reduction by G. Note that the word xu 1 vu 2 z needs not be a word from L(G).

We will often say in the following that (x, u 1 , A, v, u 2 ) is a pumping prefix and that (x, u 1 , A, v, u 2 , y) is a pumping infix.

Elementary infix etc. We say that an (x, u 1 , A, v, u 2 , y)pumping infix by G is elementary if the (x, u 1 , A, v, u 2 )pumping reduction is the only and, at the same time, the last pumping reduction by G that can be performed inside of the word xu 1 vu 2 y, i.e. xvy cannot be reduced by any pumping reduction by G at all. In this case, we say that (x, u 1 , A, v, u 2 ) is an elementary pumping prefix, and that (u 1 , A, v, u 2 ) is an elementary pumping pattern by G.

Let us note that the corresponding elementally pumping tree T 1 does contain an internal node with the same nonterminal as the root of T 1 , and does not contain any other repetition of a nonterminal on any path from its root to a leaf. While the size (the number of terminal symbols) of a pumping infix by G is unbounded, there exists a constant c > 0 that depends on the number of terminals and nonterminals, and the length of rules of G such that any elementary pumping infix by G is of size at most c.

We can see the following obvious proposition that summarizes the (pumping) properties of LR(0)-grammars, which we will use in the following text. It is a direct consequence of the previous definitions and the properties of LR(0)-grammars and their analyzers summarized in [3], and inspired by [9]. Proposition 1. Let G = (V, Σ, R, S) be an LR(0)-grammar generating (analyzing) the language L = L(G). Let a word P p = xu 1 vu 2 be an (x, u 1 , A, v, u 2 )-pumping prefix by G, and xu 1 u 1 vu 2 u 2 ⇐ P(G) xu 1 vu 2 be an (xu 1 , u 1 , A, v, u 2 )-pumping reduction by G. Then (a) Any w ∈ L determines its derivation tree T w by G unambiguously.

(b) P p determines its pumping sub-tree unambiguously. (e) An (x, u 1 , A, v, u 2 )-pumping prefix by G, and the pumping pattern (u 1 , A, v, u 2 ) determine unambiguously a single pumping reduction.

Assertion (c) is essential for our further considerations. It shows that, for a non-empty u 1 , the distance of the place of pumping from the left end is not limited, and that the position of pumping is determined both by the pumping pattern of a pumping reduction and the pumping prefix of the pumping reduction. We use this property in the following definition formalizing a non-regular type of pumping. The pumping notions can be illustrated in Fig. 2 with a derivation tree for w = xaabby ∈ L(G), where x ∈ a * ,y ∈ b * . We can see, by taking x = a, that P p = aaabb is an (a, a, S 1 , ab, b)-pumping prefix by G, and that T 1 is a pumping tree of P p . Pumping pattern of P p by G is We say that A is a distinguishing nonterminal for G, and xu 1 vu 2 ⇐ P(G) xv is an (x, u 1 , A, v, u 2 )-distinguishing reduction by G if at least one of the following conditions is true: (I) for some y ∈ Σ * there is a p > 0 such that xvy ∈ L iff xvu p j 2 y / ∈ L, for all j > 0;