We introduce context-free grammar with sentinels, CF(c| ,$)-grammar, as a generalization of recently introduced LR(c| ,$)grammar. Original LR(c| ,$)-grammars can be used to construct deterministic pumping restarting automata performing correctness and error preserving pumping analysis by reduction on each word over its input alphabet. Pumping analysis by reduction involves step-wise simplification of an input word by removing at most two continuous parts of the current word while preserving the correctness or incorrectness of the word. Each such simplification step corresponds to removing portions of the current word that can be “pumped” according to the pumping lemma for context-free languages, and thus, it does not use any nonterminals. One-side pumping grammars are CF(c| ,$)-grammars that allow removing just one continuous part in each step of pumping reduction. A complete CF(c| ,$)-grammar generates both a language and its complement with sentinels. We show that complete one-side pumping CF(c| ,$)-grammars characterize the class of regular languages, while LR(c| ,$)-grammars that allow two-side pumping reductions characterize the class of deterministic context-free languages. LR(c| ,$)-grammars that do not allow any one-side pumping reduction generate non-regular languages only.
This paper builds upon and improves the findings from papers [1, 2, 3] that introduced and investigated certain restrictions for deterministic monotone restarting pumping automata (det-mon-RP-automata). The motivation for introducing general restarting automata was to model analysis by reduction.
Analysis by reduction is a method from linguistics.
Here it serves for checking the correctness of an input word by step-wise rewriting some part of the current tape with a shorter one until we obtain a simple word for which we can decide its correctness easily. In general, analysis by reduction is nondeterministic, and in one step, we can rewrite a sub-string of a length limited by a constant with a shorter string. An input word is accepted if there is a sequence of reductions such that the final simple word is from the target language. Then, intermediate words obtained during the analysis are also accepted. Each reduction must be error preserving, i.e., no word outside the target language can be rewritten into a word from the language.
Our interest in studying pumping restarting automata was awakened by papers [4, 5] investigating the complexity of parsing deterministic context-free languages. This paper’s linguistic and non-linguistic motivations can already be found in [1, 2, 6]. We aim to develop formal tools supporting the characterization and localization of syntactical errors in artificial and natural languages.
This paper should contribute to a complete taxonomy of diferent types of syntactical errors encountered when parsing deterministic context-free languages.
In this paper, we study some types of deterministic analysis by reduction. We are mainly interested in a strongly constrained version of analysis by reduction called pumping analysis by reduction. Pumping analysis by reduction is a reduction analysis with the following additional restriction. In each step of pumping analysis by reduction, the current word is not completely rewritten.
Instead, at most two continuous segments of the current word are deleted.
When a restarting automaton works on a word, the word is always delimited by sentinels – c| on the left and $ on the right end of its tape. Therefore, we consider here context-free grammars with sentinels, shortly CF(c| ,$)grammars, that generate only words of the form {c| } · · {$}, where is a word over an alphabet Σ containing neither c| nor $.
Here, we use so-called complete CF(c| ,$)-grammars that generate all words from {c| } · Σ * · { $}. Informally, a complete CF(c| ,$)-grammar has two initial nonterminals, and . The set of words derived from the In what follows, we will work with the class of contextnonterminal is a language of the form {c| } · · { $}, free languages and some of its subclasses, like determinfor some language ⊆ Σ * . The language is called the istic context-free languages (see [8]). Let Σ be a finite inner language of . The set of words derived from the nonempty alphabet. A language ⊆ Σ * is contextnonterminal is complementary to {c| } · · { $} with free if it is generated by a context-free grammar = respect to {c| } · Σ * · { $}, that is {c| } · (Σ * ∖ ) · { $}. (, Σ , , ), where is a finite set of nonterminals, Σ
Pumping lemma for context-free languages [7] implies is a finite set of terminals, ∩ Σ = ∅, ∈ is the that, for each complete CF(c| ,$)-grammar , there exists a initial symbol, and is a finite set of rules of the form constant such that each word generated by derived → , for ∈ and ∈ ( ∪ Σ) * . from (or , respectively) of length greater than We say that directly derives (denoted as ⇒ ) can be written as a concatenation of some words 1, 2, by if = , = for some , , , , ∈ 3, 4, and 5, where 24 is nonempty, and all words ( ∪ Σ) * , ∈ and → ∈ . The reflexive and 12 34 5, for all integers ≥ 0, can be derived from transitive closure of the relation ⇒ is denoted as ⇒* . (or , respectively). Hence, during reducing pump- If, additionally, is a terminal word, we say that the ing analysis, 12345 can be reduced into 135. derivation step = ⇒ = is a rightmost If 2 or 4 is empty, we say the pumping reduction is a derivation step and denote it as ⇒r . Obviously, ⇒r* one-side reduction. denotes the reflexive and transitive closure of the relation
It is well-known that each deterministic context-free ⇒r. language can be generated by an LR(0) grammar ([7]). In For each context-free grammar = (, Σ , , ), [3], it was shown that for each deterministic context-free there exists a context-free grammar ′ = ( ′, Σ , ′, ′) language , there exists a complete CF(c| ,$)-grammar, that generates the same language as such that for which is an LR(0) grammar with the inner language . each nonterminal from ′, there is at least one word Moreover, the language is accepted by a deterministic ∈ Σ * for which it holds ⇒* and there exist restarting RP-automaton that performs pumping anal- words , ∈ ( ′ ∪ Σ) * for which it holds ′ ⇒* . ysis by reduction on all input words (both from and its We say that grammar ′ is reduced [8]. complement). The last phase of the computation of on an input word produces a terminal word ′ that is 2.1. CF(¢,$)-grammars not longer than the above constant . If c| ′$ is derived from according to , then ′ (and thus also ) is In [3], we introduced LR(c| ,$)-grammars and complete accepted by . Otherwise if c| ′$ is derived from LR(c| ,$)-grammars to provide a formal tool for identifying according to , then ′ (and thus also ) is rejected syntax errors within the analysis-by-reduction process by . performed by RP-automata. Additionally, we sought to
CF(c| ,$)-grammars that allow only left-side pumping characterize and diferentiate deterministic context-free reductions (4 is empty in all possible pumping reduc- languages (DCFL) from regular languages based on the tions) or only right-side pumping reductions (2 is empty decidable syntactic properties of the formal model. The in all pumping reductions) generate only regular lan- concept of pumping reduction emerged as a crucial eleguages. On the other hand, we show that two-side pump- ment in achieving these goals. In this section, we present ing CF(c| ,$)-grammars that are LR(0) and do not allow the definitions and results from [ 3] concerning LR(c| ,$)one-side pumping at all generate non-regular languages grammars but now in a new, more general setting of only. CF(c| ,$)-grammars.
The paper has the following structure. Section 2 intro- Definition 1. Let and Σ be two disjoint alphabets, dmuacress, tahnedmpauimnpniontgionnostoiofnCsF.(Ic|n,$S)-egcrtaiomnm3a,rws,eLsRh(0o)wgrtahmat- cc| o,n$te∈/xt-(free∪grΣ)am manadr gen=era(ting, Σ a l∪an{gc|u,a$g}e,of,the) fboerma the class of inner languages of one-side CF(c| ,$)-grammars coincides with the class of regular languages. Conversely, r{ic|g}ht·-ha· n{d$s}i,dwehoefraeny ⊆ rulΣe* f,roamnd. dWoees snaoyt othccautrinitshae Section 4 shows that the inner language of a complete CF(c| ,$)-grammar. The language is the internal language CF(c| ,$)-grammar, which is LR(0) and does not allow any of , and it is denoted as in(). W.l.o.g., we suppose that one-side pumping reduction, is not regular. Section 5 a CF(c| ,$)-grammar does not contain rewriting rules of the presents further results dealing with one- and two-side form → for any nonterminal ∈ , where denotes pumping grammars. Section 6 concludes the paper and the empty word. sketches directions for further research.
Closure properties of the class of context-free languages imply that for a CF(c| ,$)-grammar , both languages () and in() are context-free. The added Proof: (Sketch) Let ∈ () and be a derivation right sentinel $ facilitates recognition of languages. E.g., tree with the symbols of in its leaves. if is a deterministic context-free language, then it can In , if there is no path from its root to a leaf on which be generated by an LR(1)-grammar (see [7]). But · { $} two nodes are labeled with the same nonterminal, then and {c| }· ·{ $} are both generated by simpler LR(0) gram- the lemma statement holds for = 1, as there is no mars. The left sentinel c| is included in CF(c| ,$)-grammars pumping reduction possible. for compatibility with RP-automata. Suppose there is a path from the root of to a leaf such that two nodes on the path are labeled with the same 2.2. Pumping Notions of nonterminal . In that case, we can build a pumping CF(¢,$)-grammars infix (, 1, , , 2, ) (for some , 1, , 2, ∈ Σ * and ∈ ) by such that = 12, then = This section studies the pumping properties of CF(c| ,$)- 12 ⇝ () and the derivation tree can be grammars. We start with several definitions and nota- modified into the derivation tree 1 for the word by tions. replacing the subtree corresponding to the derivation of
Let = (, Σ ∪ {c| , $}, , ) be a CF(c| ,$)-grammar, ⇒* 12 with the subtree for the derivation ⇒* , 1, , 2, be words over Σ , |1| + |2| > 0, || > 0, . Further, we can again try to find a path with repeating and ∈ be a nonterminal. If nonterminal in tree 1 and construct another pumping reduction. In this way, we can continue until we obtain ⇒* c| $ ⇒* c| 12$ ⇒* c| 12$ (1) a word with a derivation tree, in which there is no path with repeating nonterminal. In this way, we obtain the desired sequence of pumping reductions. □ we say that (, 1, , , 2, ) is a pumping infix by , 12 ⇝ () is a pumping reduction by and the word c| 12$ is a pumped word according to .
Note that we omitted the sentinels in the pumping Definition 2. Let (, 1, , , 2, ) be a pumping infix infix and pumping reduction, and 12 ∈ in(). by a CF(c| ,$)-grammar . We say that the pumping infix
The relation ⇝ * () is the reflexive and transitive clo- is a core pumping infix if there is a derivation tree by sure of the relation ⇝ (). that corresponds to the derivation infixObnytheo,tthheernhaallnwd,oirfd(so,ft1h,efo,rm,c|2,1)is2ap$u, mfoprinalgl ⇒* c| $ ⇒* c| 12$ ⇒* c| 12$ (2) integers ≥ 0, belong to (). such that the path between the root 1 of the subtree corre
We call pumped each derivation tree corresponding sponding to the derivation of 12 from in (2) to the to a derivation of the form (1). Likewise, we say that root 2 of the subtree corresponding to the derivation of the word c| 12$ is pumped, and the derivation (1) (but without 2) does not contain two distinct nodes labeled is pumped. with the same nonterminal.
Let = (, Σ ∪ {c| , $}, , ) be a CF(c| ,$)-grammar, We write 12 ⇝ (,core) , and say that the be the number of nonterminals of , and be the maxi- reduction 12 ⇝ (,core) is a core pumping mal length of the right-hand side of the rules from . Let reduction by . The transitive and reflexive closure of be a derivation tree according to . If has more than ⇝ (,core) is denoted in the standard way as ⇝ * (,core). leaves, a path exists from a leaf to the root of such that it contains at least + 1 nodes labeled by nontermi- Note that in the above derivation (2), the length of the nals. As has only nonterminals, at least two nodes words , 1, , 2, is not limited. A general pumpon the path are labeled with the same nonterminal . In ing reduction ⇝ () ′ corresponds to removing a that case, there is a derivation of the form (1), and is segment between any nodes 1 and 2 labeled with the a pumped derivation tree. We say that = is the same nonterminal occuring on a path from the root of grammar number of . a derivation tree for . The pumping reduction is core if
Note that for any word from () of length greater there is no other node labeled with between 1 and 2, than , some pumping infix by must correspond. and all nodes between 1 and 2 are labeled with distinct On the other hand, each word generated by that is not nonterminals. The statement of Lemma 1 can be easily pumped is of length at most . extended to pumping analysis using core reductions only. Lemma 1. Let = (, Σ ∪ {c| , $}, , ) be a CF(c| ,$)- Corollary 1. Let = (, Σ ∪ {c| , $}, , ) be a grammar. If generates , then there exists a sequence CF(c| ,$)-grammar. If generates , then there exists a of words 1, . . . , from (), for some integer ≥ 1, sequence of words 1, . . . , from (), for some insuch that = 1, there are pumping reductions teger ≥ 1, such that = 1, there are core pumping ⇝ () +1, for all = 1, . . . , − 1, and there reductions ⇝ (,core) +1, for all = 1, . . . , − 1, is no +1 ∈ Σ * such that ⇝ () +1. and there is no +1 ∈ Σ * such that ⇝ () +1.
CF(c| ,$)-grammar. We say that is a left-side pumping CF(c| ,$)-grammar if all its core pumping infixes are leftside pumping infixes. Similarly, we say that is a rightside pumping CF(c| ,$)-grammar if all its core pumping infixes are right-side pumping infixes. We say that is a one-side pumping CF(c| ,$)-grammar if it is left-side or right-side pumping CF(c| ,$)-grammar. If is neither left-side nor right-side pumping grammar, we say that is a two-side pumping CF(c| ,$)-grammar. 2.3. Complete CF(¢,$)-grammars In this subsection, we generalize complete LR(c| ,$)-grammars from [3] to complete CF(c| ,$)-grammars.
A complete CF(c| ,$)-grammar is a grammar that enables analysis of a language and its complement. If a complete CF(c| ,$)-grammar is used in an analytic mode, it returns a derivation tree for each input word of the form c| $, where ∈ Σ * . The nonterminal under their root distinguishes the accepting and rejecting analytic trees.
That means that the accepted words have accepting trees only, and the rejected words have rejecting trees only.
Definition 4. Let = (, Σ ∪ {c| , $}, , ) be a CF(c| ,$)-grammar. Then is called a complete CF(c| ,$)grammar if
However, every word from (′) can be reduced to c| $ or c| $ using left-side core pumping reductions, where the nonterminal is not used. • a one-side pumping infix if 1 = , or 2 = , Interestingly, after omitting all rules that include from • a two-side pumping infix if 1 ̸= , and 2 ̸= , the grammar, we obtain a one-side (more precisely, left• a left-side pumping infix if 2 = , and side) pumping grammar generating the same language as • a right-side pumping infix if 1 = . the original grammar.
Evidently, (′) = {c| } · { , }+ · { $}. is a core two-side (left-side or right-side, respectively) pump
Consider the pumping infix (, , , , , ). This ing infix by , then there is a two-side (left-side or rightpumping infix is a core and two-side pumping infix; there- side, respectively) core pumping infix by for a word of fore, grammar ′ is a two-side pumping grammar. length at most 3.
Example 1. Let = ({, ′, }, {, , , c| , $}, , ) be a CF(c| ,$)-grammar, where is the set of rules: → c| ′$,
′ → | , → ′ | ′.
The grammar is a two-side pumping grammar. All its core pumping infixes are of one of the following forms: (, , ′, ′, , ), (, , ′, ′, , ), (, , , , , ) or (, , , , , ), for any words ∈ {}* , ∈ {}* , , ′ ∈ {}* · · { }* , || ≥ 2. All the core pumping infixes are one-side, but the grammar is two-side pumping as it has both left-side and right-side pumping infixes. We will denote the grammar as = (, ). Further,
There also exist two-side pumping infixes by , like we will call and as accepting and rejecting gram 1 = (, , ′, , , ) or 2 = (, , , , , ). mar of the complete CF(c| ,$)-grammar , respectively. The former is not core pumping infix since there is a path between two nodes labeled with ′ (from which ′ and Obviously, for each word of the form c| $, where ∈ are derived) in the corresponding derivation tree containing Σ * , there is some derivation tree according to . The another node labeled with ′. Similarly, the derivation tree node under the root of is labeled either by or . If corresponding to the pumping infix 2 contains a sub-path it is , the word is generated by the accepting grammar between nodes labeled with (from which and . Otherwise, it is generated by the rejecting grammar are derived) that contains another node labeled with . .
Moreover, for each word, two or more derivation trees Example 2. Let ′ = ({, , }, {, , c| , $}, , ) be can exist, but all of them are accepting, or all of them are a CF(c| ,$)-grammar with the following set of rules: rejecting.
The following lemma will be used below to show that we can decide if a given complete CF(c| ,$)-grammar is one-side CF(c| ,$)-grammar.
1. → | , where , ∈ , are the only rules in containing the initial nonterminal . No other rule of contains or in its righthand side. 2. The languages () and () generated by the grammars = (, Σ ∪ {c| , $}, , ) and = (, Σ ∪ {c| , $}, , ), respectively, are disjoint and complementary with respect to {c| } · Σ * · { $}. That is, () ∩ () = ∅ and ( ) = () ∪ () = {c| } · Σ * · { $}. → c| $ | c| $, → | , → | | | .
Proof: Let = (, 1, , , 2, ) be a two-side core pumping infix by . There is a derivation tree corresponding to a derivation ⇒* c| $ ⇒* c| 12$ ⇒* c| 12$ (3) → in , where ∈ is included in . Note that ℰ can contain loops and |ℰ | = (||).
Let Σ 1 = Σ ∪ {c| , $}. Define the function ℓ : ℰ → 2{left,right,both} such that for each = (, ) ∈ ℰ , • left ∈ ℓ() if there is a rule → in , where
, ∈ and ∈ ( ∪ Σ 1)+, • right ∈ ℓ() if there is a rule → in ,
where , ∈ and ∈ ( ∪ Σ 1)+, and • both ∈ ℓ() if there is a rule → where , ∈ and , ∈ ( ∪ Σ 1)+. where the sub-path 1,2 between the root 1 of the subtree corresponding to a derivation of 12 from to the root 2 of the subtree corresponding to the derivation of (but without 2) in (3) does not contain two distinct nodes labeled with the same nonterminal. in ,
Suppose there are two distinct nodes on the path 1 between the root of and the node 1 labeled with the Let = (1, . . . , ) be a directed walk in such same nonterminal. In that case, we can perform the that = (− 1, ) ∈ ℰ , for = 1, . . . , . As is corresponding pumping reduction and still preserve a reduced, there exists a derivation tree for containing two-side pumping infix in the reduced derivation tree. a path = (1, . . . , ), where = (− 1, ), for
Similarly, let be a path between an arbitrary leaf some nodes 0, . . . , of such that the nodes on (including leaves under 2) and the closest node on the are labeled with nonterminals 0, . . . , . path 2 between the root of and 2. If contains Based on Definition 2 of core pumping infix, we can two distinct nodes labeled with the same nonterminal, conclude that is a left-side pumping grammar if and we perform the corresponding pumping reduction. In only if, for each walk = (1, . . . , ) in starting the obtained derivation tree, we can still find a two-side and ending in the same node, it holds core pumping reduction, as the pumping reduction does not delete any node from the sub-path 1,2 . Note that ⋃︁ ℓ() ⊆ { left}. (4) is reduced and, according to Definition 1, does not ∈ contain any rule of the form → . Hence, a reduction on a path from a leaf to a node on the path 2 (path Similarly, is a right-side pumping grammar if and contains only one node from 2 ) cannot delete all only if for each walk = (1, . . . , ) in starting terminal leaves of the corresponding subtree. and ending in the same node it holds
In this way, we obtain a derivation tree with a two-side pumping infix of height at most 3, where is the number ⋃︁ ℓ() ⊆ { right}. (5) of nonterminals of . Such a tree has at most 3 = 3 ∈ leaves.
The proofs for left-side and right-side pumping infixes are similar. □
Obviously, all edges from are in the same strongly connected component of graph . We can construct all strongly connected components of graph using Tar
Lemma 2 implies that we can decide whether given jan’s algorithm [9] in time (|| + |ℰ |) = (||). Then, CF(c| ,$)-grammar is one-side pumping grammar by in- for each strongly connected component , we can test specting all pumping infixes in all derivation trees for whether satisfies the condition (4) or (5) in time linwords of length at most 3. Below we show how to do ear with the size of . Hence, we can decide whether such a test more eficiently. grammar is one-side in time (|| + |ℰ |) = (||).
For a context-free grammar = (, Σ , , ), we □ define its size as || = ∑︀∈ ||, where || denotes the number of terminals and nonterminals in the rule , including the left-hand side nonterminal, i.e., if = → 2.4. LR(0) Grammars , where ∈ and ∈ (Σ ∪ )* , then || = 1 + | |.
Theorem 1. Let = (, Σ ∪{c| , $}, , ) be a reduced CF(c| ,$)-grammar. An algorithm that runs in (||) time can decide whether is one-side pumping.
Proof: As grammar is reduced and does not have any rule with the empty right-hand side, each nonterminal can be used in some derivation, and from each nonterminal, only nonempty terminal strings can be derived.
We construct a directed graph = (, ℰ ) as follows: = , and (, ) ∈ ℰ if and only if there is a rule One of the main results of this paper strongly utilizes the theory of LR(0) grammars [7]. For any LR(0) grammar , we can construct a deterministic parser that not only accepts each word ∈ () but also produces a unique derivation tree for . Then, with such a derivation tree, we can unambiguously associate the rightmost derivation of the word according to .
Let us recall the definition and properties of LR(0) grammars from [7].
Definition 5 ([7]). Let = (, Σ , , ) be a contextfree grammar and ∈ ( ∪ Σ) * . A handle of is an ordered pair (, ), ∈ , ≥ 0 such that there exists ∈ , , ∈ ( ∪ Σ) * and ∈ Σ * such that (a) ⇒r* ⇒r (b) = → , and (c) = | |.
= , class of languages generated/accepted by grammars/automata from . Similarly, for (sub)class of CF(c| ,$)grammars we denote ℒin() = { | {c| } · · { $} ∈ ℒ()}.
Based on the closure properties of DCFL shown, e.g., in [7], internal languages of LR(c| ,$)-grammars can be used to represent all deterministic context-free languages.
Proposition 1 ([3]). ℒin(LR(c| , $)) = DCFL.
While a handle in a string is generally not uniquely deifned, this is not the case for LR(0) grammars.
Thus, if is an LR(0) grammar, then the rightmost derivation of the word by and the left-right analysis are unique (deterministic). This paper considers (0) grammars to a significant extent as analytical grammars.
A language generated by an LR(0) grammar is called LR(0) language.
It is shown in [7] that every LR(0) language is deterministic context-free, and for each deterministic context-free language ⊆ Σ * and symbol $ ̸∈ Σ , the language · { $} is LR(0). The construction of an “LR-style parser” is also given there. The parser is a deterministic pushdown automaton that reads the input word from left to right and stores the partially processed prefix of the input word in its stack until the right-hand side of the rewriting rule of the grammar is identified, and the right-hand side is then replaced with the corresponding left-hand side.
The input word is accepted if it is reduced to the starting nonterminal in its stack.
In literature, several automata models were based on the analysis by reduction. In [3], we introduced so-called RP-automata, the restarting automata [2] that difer only slightly from the original RW-automata introduced in [10] and from reducing automata presented in [11]. RPautomata perform only pumping reductions. 2.5. LR(¢,$)-grammars Definition 7. Let c| , $ ∈/ ( ∪ Σ) and = (, Σ ∪ {c| , $}, , ) be a CF(c| ,$)-grammar that is also LR(0) grammar. We say that is an LR(c| ,$)-grammar.
Classes of languages. In what follows, ℒ(), where is some (sub)class of grammars or automata, denotes the
Example 3. Consider the non-regular deterministic context-free language = {c| $ | ≥ 1} with the internal language in = { | ≥ 1} that is generated by the reduced LR(c| ,$)-grammar = ({, 1, , }, {, } ∪ {c| , $}, , ), with the set of rules : 1 → → c| 1$, 1 | .
Consider the sentence = c| $. For example, the pair (1 → , 5) is a handle of (cf. Definition 5), as ⇒r* c| 1$ ⇒r c| $ and the division of into , , is unique: = c| $ .
⏟ ⏞ ⏟ ⏞ ⏟ ⏞ We can see that is a linear LR(c| , $)-grammar, as (a) ⇒r* ⇒r = , and (b) ⇒r* ′′ ⇒ ′ ′ = ′
r obviously implies ( → , | |) = (′ → ′, | ′ ′|), because = 1, = , = , = 1, for some ≥ 0.
Fig. 1 illustrates the pumping infix (, , 1, , , ) in a derivation tree for = c| $ ∈ (), where = , = , for any ≥ 0.
This section will show that left-side and right-side pumping CF(c| ,$)-grammars generate only regular languages. At first, we will study the rightmost derivations according to right-side pumping CF(c| ,$)-grammars. 1 1 c| $
Lemma 3. Let = (, Σ ∪{c| , $}, , ) be a right-side pumping CF(c| ,$)-grammar. Let Σ 1 = Σ ∪ {c| , $}, be the maximal length of the right-hand side of the rules of and = | |. Let, for some ≥ 1, ∈ ( ∪ Σ 1)* · , ∈ Σ *1, for all = 1, . . . , ,
r r ⇒ 11 ⇒ · · · ⇒ r − 1− 1 ⇒r (6) be a rightmost derivation of a terminal word ∈ Σ *1 according to . Then, each is of length at most , for all = 1, . . . , − 1. rule of the form → , and 1 contains at least a terminal string derived from 1 . Hence, is not right-side pumping infix – a contradiction with the assumption that is right-side pumping CF(c| ,$)-grammar. □
ping CF(c| ,$)-grammar is regular.
Proof: Let = (, Σ ∪ {c| , $}, , ) be a right-side pumping CF(c| ,$)-grammar. Let Σ 1 = Σ ∪ {c| , $}, be the maximal length of the right-hand side of the rules of and = | |.
We will construct a regular (left-linear) grammar ′ = ( ′, Σ 1, ′, ′) generating the same language as . The set of nonterminals ′ will consist of sequences of nonterminals and terminals of enclosed in square brackets.
We will construct ′ inductively.
Let ′ = [], ′ = ⋃︀∞=0 ′ and ′ = ⋃︀∞=0 ′ (we use infinite unions, but we will see below that both ′ and ′ will be finite) 0′ = {[]} ∪ {[ ] | → ∈ }, 0′ = {[] → [ ] | → ∈ }.
For ≥ 0, let Proof: For a contradiction, assume | | > , that is ( ∪= Σ 1)1,· · ·and,wh∈ere ,for>som,e1b,e.t.w. e,en1− 1an∈d ′+1 = ′ ∪{[ ] | [∃ ∈]∈,,′ and∈(→∪ Σ ∈1)* }: − 1. Consider the partial derivation tree correspond- ∪{[ ] | ∃ ∈ Σ *1 : [ ] ∈ ′}, ing to the sentential form 1 · · · . Let ( ) de- ′+1 = ′ ∪{[ ] → [ ] | ∈ , [ ] ∈ ′, note the parent node of the node labeled with , for , ∈ ( ∪ Σ 1)* : sib=le1t,h.a.t.s,eve.rAalsn(6o)diessalarbigehletdmwositthderi1v,a.t.io. n,,itishpaovse- ∪{[ ] → [ ] | ∈→( ∈∪ Σ1})* · , a common parent, but at most nodes have the same ∈ Σ 1+ : [ ] ∈ ′} parent, as is the maximal length of a rule in .
We will show that ( ) is on the path from the root ∪{[] → | ∈ Σ *1, [] ∈ ′}. of to (), for all = 1, . . . , . If [ ] is a nonterminal from ′, then is a substring of
Let us suppose that ( ) is not on the path from a sentential form obtained during a rightmost derivation the root of to (). Then, let , ̸= ( ), denote ⇒r* according to , for some ∈ ( ∪ Σ 1)* , the closest ancestor of ( ) and () in . The ∈ Σ *1. nodes labeled with and are descendants of two Either, [ ] = [ ] was obtained by rewriting [ ], diferent child nodes of . for some ∈ , [ ] ∈ ′, and → ∈ . Then,
Obviously, the nodes ( ) and () are labeled according to Lemma 3, cannot be longer than . by nonterminals. As (6) is a rightmost derivation, the Thus is of length at most + − 1. node ( ) cannot be rewritten before rewriting the Or, [ ] = [ ] was obtained by rewriting [ ], for some nonterminal into a terminal string. Hence, ( ) = ∈ ( ∪ Σ 1)* · , ∈ Σ 1+. Then, according to Lemma and ( ) is on the path . 3, cannot be longer than .
Thus, the set = {(1), . . . , ()} contains In both cases, if [ ] is a nonterminal from ′, for some more than > = nodes, and all of them are on the ∈ ( ∪ Σ 1)* , then the length of is limited by a path . There exist two nodes (1 ) and (2 ) in , constant. Hence, ′ and ′ are finite sets. (1 ) ̸= (2 ), labeled with the same nonterminal It is easy to show that, for all ∈ ( ∪ Σ 1)* , ∈ , such that between the nodes (1 ) and (2 ), there , ∈ Σ *1, it holds: is no other node labeled with . Then, there is a core pumping infix = (, 1, , , 2, ) by such that ⇒r* ⇒r* if [] ⇒* [ ] ⇒* . 1 is nonempty, as is reduced, does not contain any
Let us illustrate the construction from the above proof by an example.
Example 4. The grammar = ({, , , }, {, , , c| , $}, , ) with the set of rules : → c| $, → | , → | , → . is a right-side pumping CF(c| ,$)-grammar. We can construct an equivalent left linear grammar ′ with the following set of rules: [] → [c| $], [c| $] → [c| ]$, [c| ] → [c| ] | [c| ], [c| ] → c| , [c| ] → [c| ] | [c| ], [c| ] → [c| ], [c| ] → [c| ], [c| ] → [c| ], [c| ] → [c| ] | [c| ], [c| ] → [c| ], [c| ] → [c| ].
pumping CF(c| ,$)-grammar is regular.
Proof: Let = (, Σ ∪ {c| , $}, , ) be a left-side pumping CF(c| ,$)-grammar. Then the CF(c| ,$)-grammar (R) = (, Σ ∪ {c| , $}, , (R)) obtained by reversing the right-hand sides of all rules of , except that the sentinels c| and $ must not change their positions in the rules, generates the language ((R)) = {c| }· [in()]R · {$} and (R) is a right-side pumping CF(c| ,$)-grammar. Lemma 4 says the language ((R)) is regular. The closure of the class of regular languages on quotients, reversal, and concatenation implies that () is regular, too. □
We get the following theorem as a simple consequence of Lemma 4 and Corollary 2.
Theorem 3. Let = (, ) be a complete oneside pumping CF(c| ,$)-grammar. Then, both () and in() are regular languages. → 1 → c| 1$ | c| 1 | 2$, 1 → 1 | , 2 → 1 | 1$, 2 | c| 1.
tions. (1) = {c| $ | > 0, > 0} and (1) obviously is a regular language.
The same language can, of course, be generated by the following left-side pumping grammar with starting nonterminal and the following set of rules: → 2 → c| 1, 2 | $.
1 → 1 | 2
duced CF(c| ,$)-grammar is called totally two-side pumping if there is at least one two-side core infix and no one-side pumping infix by .
Example 6. Let be the following CF(c| ,$)-grammar with starting nonterminal , further nonterminals , , terminal alphabet Σ 1 = Σ ∪ {c| , $}, for Σ = {, }, and rules: → c| $, → | | | , → | .
(, 1, , , 2, ), where 1, 2 ∈ Σ , , , ∈ Σ * such that either = , || is odd and || = ||, or = , || is even and || = || + 1.
Thus, grammar is a totally two-side pumping CF(c| ,$)grammar that generates the regular language () = {c| $ | ∈ {, }2+1 for some ≥ 0}. But is not an LR(c| ,$)-grammar.
For a pumping infix (, 1, , , 2, ), we say that 12 is its middle part. Realize that although the length of core pumping infix is potentially unbounded, it is possible to identify core infixes with the length of their middle part limited by a constant. Such pumping infixes will be called bottom pumping infixes.
Thus () = (′), the grammar ′ is left linear and Example 5. Consider the linear LR(c| ,$)-grammar 1 gigenerates a regular language, and () is a regular lan- ven by the following rules, where is the starting nonterguage. □ minal: Definition 8. Let be a CF(c| ,$)-grammar and = (, 1, , , 2, ) be a pumping infix by . We say that 4. Two-Side Pumping is a bottom pumping infix if there is no other pumping infix reducing inside its middle part 12. That is, if there Theorem 3 has a straightforward consequence: non-regu- are terminal words 1, ′1, ′, ′2, 1 and a pumping infix lar languages cannot be generated with one-side pumping ′ = (1, ′1, , ′, ′2, 1) by such that grammars.
Corollary 3. Let = (, Σ ∪ {c| , $}, , ) be a CF(c| ,$)-grammar such that in() is a non-regular language. Then is a two-side pumping grammar.
The opposite is not true – two-side pumping grammars can generate regular languages.
12 = 1′1′′21 then ′ = .
Correspondingly, we say that a pumping reduction is a bottom pumping reduction if the corresponding pumping infix is a bottom pumping infix. We write 1121 ⇝ (,bottom) 11.
Let = (, 1, , , 2, ) be a pumping infix, and Since has states, within its accepting computation be a derivation tree by the grammar correspond- on , where > , automaton visits at least two ing to . The tree has a subtree 12 that derives occurrences of (in front of 1) in the same state. Thus, the middle part 12. The pumping infix is a bot- there is a positive integer such that 0 < < + tom pumping infix if and only if the subtree 12 has 1, and for each non-negative integer , the word ′ = exactly one path from its root to its leaf on which two c| (1)· (1)+1(2)+1$ is in (). diferent nodes are labeled with the same nonterminal. Let 0 be an integer greater than (3 + 2). Let Hence, the height of 12 is at most + 1, where is us consider the derivation tree by for the word the number of nonterminals of . Therefore, the length = 0++1 and the derivation tree by for the of the middle part 12 is at most +1 = · , where word = ′0 . The words and have the common is the maximal length of the right-hand side of the rules prefix = c| (1)0++1(2)+1. of and is the grammar number of . According to Corollary 4, there is a sequence of the
Evidently, each bottom pumping infix by is a core bottom core pumping reductions ⇝ (,bottom) +1, pumping infix by , and we could prove a stronger ver- for = 1, . . . , − 1 and 1 = , and there is no +1 ∈ sion of Corollary 1. Σ * such that ⇝ () +1. Suppose it is the leftmost sequence of core bottom pumping reductions.
Corollary 4. Let = (, Σ ∪ {c| , $}, , ) be a Similarly, for the word , there is a sequence of the leftCF(c| ,$)-grammar. If generates , then there exists a se- most bottom core pumping reductions ⇝ (,bottom) quence of words 1, . . . , from (), for some integer +1, for = 1, . . . , − 1 and 1 = , and there is no ≥ 1, such that = 1, there are bottom pumping re- +1 ∈ Σ * such that ⇝ () +1. ductions ⇝ (,bottom) +1, for all = 1, . . . , − 1, The initial part of the sequence of the leftmost core botand there is no +1 ∈ Σ * such that ⇝ () +1. tom pumping reductions starting from 1 until the first
Now we can show that in contrast to general two-side pumping reduction that uses a middle part that contains pumping CF(c| ,$)-grammars, totally two-side pumping a symbol outside the prefix makes the same changes LR(c| ,$)-grammars cannot generate regular languages. as the initial part of the sequence of the leftmost core bottom pumping reductions starting from 1 until the Theorem 4. Let be a reduced totally two-side pumping first pumping reduction uses a middle part that contains LR(c| ,$)-grammar. Then () is not a regular language. a symbol outside the prefix .
In the case of , after the common prefix of the seProof: Let = (, Σ ∪ {c| , $}, , ) be a reduced to- quence of bottom core pumping reductions, the subsetally two-side pumping LR(c| ,$)-grammar. There is at quent reductions will continue deleting pairs of subwords least one two-side core pumping infix by . For a con- 1 and 2. In the case of , the following pumping tradiction, suppose that () is a regular language. We reductions must delete most of c| (1)0 and $. will show that there exists at least one one-side pumping Let us inspect the derivation tree . Let = {, 1, infix by , which contradicts the assumption that is . . . , , } be the set of all maximal subtrees of such totally two-side pumping. that all their leaves are in c| (1)0 . The set of subtrees
If () is a regular language, there is a deterministic is nonempty, and one of the trees in contains c| . ifnite automaton such that ( ) = (). Let Let = {, 1, . . . , , } be the set of all maximal denote the number of states of . subtrees of such that all their leaves are in c| (1)0 .
Let = (, 1, , , 2, ), where , ∈ Σ , , 1, The set of subtrees is nonempty, and one of the trees , 2, ∈ Σ * , be a two-side bottom core pumping infix in contains c| . by such that ||, || ≤ 3. Such bottom pumping Additionally, the sets and are equal. Why? Beinfix exists as is reduced, has at least one two-side cause they are built during LR(0) analysis of the prefix , pumping infix ′, and, according to Lemma 2, there exists all reductions are made by the corresponding determina two-side pumping infix ′′ by for a word of length at istic LR(0) analyzer when it scans the prefix . most 3. We can suppose that ′′ is a bottom pumping For , the series of core bottom pumping reductions infix. If not, we can perform a finite sequence of pumping can continue with pumping reductions corresponding reductions that shorten all paths with repeated nontermi- to pumping infixes of the form . In , we can find nal except the one corresponding to a two-side pumping a series of bottom core reductions that delete (most of) infix until we get a bottom core pumping infix . (1)0 . However, all these reductions in must have As is a pumping infix by , all words the middle part that includes at least one symbol from = c| (1)(2)$, for ≥ 0, the sufix = $. If any of these reductions do not include any symbol from in its middle part, they must are in (). Since is an LR(0) grammar, exactly one have already been done in the sequence of reductions derivation tree exists for each word from (). performed inside the prefix .
Each bottom pumping reduction can shorten the current word by at most · symbols (the upper limit of the length of the middle part of a bottom pumping infix).
Hence, the sequence of reduction is of length at least 0 · | 1| + || > (3 + 2) ·
= 3 + 2.
As the sufix of is of length at most 3 + 1, at least one of these bottom reductions does not delete any symbol from , while its middle part must include at least one symbol from . Such bottom reduction is a left-side pumping reduction.
We have proved that if a two-side LR(c| ,$)-grammar accepts a regular language, then it has at least one core left-side pumping reduction. □
A CF(c| ,$)-grammar is totally two-side pumping if it only has two-side pumping infixes. A slight modification of the procedure from the proof of Theorem 1 gives an algorithm that decides whether is totally two-side pumping grammar in (||) time.
We use the following notations for our types of contextfree grammars. Prefix lin- denotes the linear CF-grammars, similarly 1s- the one-side pumping CF-grammars, lfs- the left-side pumping CF-grammars, rs- the right-side pumping CF-grammars, and ttsp- the totally two-side pumping CF(c| , $)-grammars.
Moreover, we denote the set of accepting grammars of complete CF(c| ,$)-grammars as CCFA.
ℒin(1s-LR(c| , $)) = ℒin(lfs-LR(c| , $)) = ℒin(rs-LR(c| , $)) = REG. ℒin(1s-CCFA) = ℒin(lfs-CCFA) = ℒin(rs-CCFA) = REG.
Proof: The corollary is a consequence of Theorem 3 and of the fact that for each regular language , there exists a left-linear LR(0) grammar and a right-linear LR(0) grammar that both generate . Recall that regular languages are closed on both left and right quotients. □
The next result follows from the previous proof.
ℒin(lin-1s-LR(c| , $)) = ℒin(lin-lfs-LR(c| , $)) = ℒin(lin-rs-LR(c| , $)) = REG. ℒin(lin-1s-CCFA) = ℒin(lin-lfs-CCFA) = ℒin(lin-rs-CCFA) = REG.
Corollary 7. ℒin(lin-ttsp-LR(c| , $)) ⊂ ℒin(lin-LR(c| , $)) ⊂ ℒ in(LR(c| , $)) = DCFL. Proof: We can see that each language from ℒin(lin(c| , $)) is a linear context-free language. On the other hand, the Dyck language is from DCFL, and it is not a linear context-free language [7]. The class ℒin(lin-ttsp(c| , $)) does not contain any regular language. On the other hand, the class ℒin(lin-LR(c| , $)) contains all regular languages. □
ℒin(ttsp-LR(c| , $)) ⊂ ℒ in(LR(c| , $)) = DCFL. Proof: Strictness of the inclusion follows from the fact that the class ℒin(ttsp-LR(c| , $)) does not contain any regular language, and the class ℒin(LR(c| , $)) contains all regular languages. □
The class of context-free languages is not closed on complement. Hence, complete CF(c| ,$)-grammars generate only a subset of the class of context-free languages as their inner languages. Nevertheless, they can also generate languages that are not deterministic contextfree languages. We give an example of complete CF(c| ,$)grammar = (, ) such that in() and its complement are non-regular (nondeterministic) context-free languages.
ing the language {c| $ | 0 < ≤ ≤ 2}. It is well known that this language is not a deterministic context-free language.
→ c| 1$, 1 → 1 | 1 | | .
{c| $ | 0 ≤ < } ∪ {c| $ | > 2 ≥ 0} ∪ (c| {, }* {, }* $) ∪ c| $.
The grammar with the starting symbol has the following rules: → c| 2$, → c| 4$, 2 → 2 | 3, 4 → 4 | 4 | , 3 → 3 | , 5 5 → → → c| 5$ | c| $, , 5 | 5 | 5 | 5.
⊂ ℒ (CCFA) ⊂ .
Proof: The first proper inclusion follows from the previous example, and the second one follows from the fact that the class of context-free languages is not closed under complement. □
In this paper, we introduced and studied complete CF(c| ,$)grammars. We have shown that left-side pumping complete CF(c| ,$)-grammars and right-side pumping complete CF(c| ,$)-grammars characterize regular languages. On the other hand, general pumping LR(c| ,$)-grammars characterize DCFL, and totally two-side pumping LR(c| ,$)grammars generate non-regular deterministic contextfree languages only. These results imply similar results for one-side pumping and two-side pumping RP(LR(c| ,$))automata from [3].
Next, we will focus on studying the regular and nonregular characteristics of two-side core pumping patterns in RP(LR(c| ,$))-automata and CF(c| ,$)-grammars. We aim to utilize these characteristics to develop tools for effective localization of syntactic errors in deterministic context-free languages (DCFL). We will demonstrate that restarting automata can serve as error-sensible analyzers for complete CF(c| ,$)-grammars.
Finally, we aim to present a construction that transforms a monotone restarting automaton with pumping properties into a complete LR(c| ,$)-grammar, while maintaining the same analysis by reduction and recognizing the same languages. A preliminary step towards this goal was already taken in [11]. of pumping patterns, in: B. Brejová, L. Ciencialová, M. Holena, F. Mráz, D. Pardubská, M. Plátek, T. Vinar (Eds.), Proceedings of the 21st Conference Information Technologies – Applications and Theory (ITAT 2021), volume 2962 of CEUR Workshop Proceedings, CEUR-WS.org, 2021, pp. 140–146. URL: http://ceur-ws.org/Vol-2962/paper05.pdf . [3] M. Plátek, F. Mráz, D. Pardubská, D. Průša, On pumping RP-automata controlled by complete LRG(¢, $)-grammars, in: L. Ciencialová, M. Holena, R. Jajcay, T. Jajcayová, F. Mráz, D. Pardubská, M. Plátek (Eds.), Proceedings of the 22nd Conference Information Technologies – Applications and Theory (ITAT 2022), volume 3226 of CEUR Workshop Proceedings, CEUR-WS.org, 2022, pp. 111–121.
URL: https://ceur-ws.org/Vol-3226/paper13.pdf . [4] J. Šíma, M. Plátek, One analog neuron cannot recognize deterministic context-free languages, in: T. Gedeon, K. W. Wong, M. Lee (Eds.), Neural Information Processing – 26th International Conference, ICONIP, Proceedings, Part III, volume 11955 of Lecture Notes in Computer Science, Springer, 2019, pp.
77–89. doi:10.1007/978-3-030-36718-3\_7. [5] P. Jančar, J. Šíma, The simplest non-regular deterministic context-free language, in: F. Bonchi, S. J. Puglisi (Eds.), 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, pp. 63:1– 63:18. doi:10.4230/LIPIcs.MFCS.2021.63. [6] M. Lopatková, M. Plátek, P. Sgall, Towards a formal model for functional generative description: Analysis by reduction and restarting automata, Prague Bull. Math. Linguistics 87 (2007) 7–26. URL: http: //ufal.mf.cuni.cz/pbml/87/lopatkova-et-al.pdf . [7] M. A. Harrison, Introduction to Formal Language
Theory, Addison-Wesley, USA, 1978. [8] J. Hopcroft, J. Ullman, Introduction to Automata
Theory, Languages, and Computation, Addison
Wesley, N. Reading, MA, 1980. [9] R. E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 1 (1972) 146–160. doi:10.1137/0201010. [1] F. Mráz, D. Pardubská, M. Plátek, J. Šíma, Pump- [10] P. Jančar, F. Mráz, M. Plátek, J. Vogel, On monoing deterministic monotone restarting automata tonic automata with a restart operation, J. Auand DCFL, in: M. Holena, T. Horváth, A. Kele- tom. Lang. Comb. 4 (1999) 287–311. doi:10.25596/ menová, F. Mráz, D. Pardubská, M. Plátek, P. Sosík jalc-1999-287. (Eds.), Proceedings of the 20th Conference Infor- [11] M. Procházka, On reducing automata and their mation Technologies – Applications and Theory normalizations, in: L. Ciencialová, M. Holena, R. Ja(ITAT 2020), volume 2718 of CEUR Workshop Pro- jcay, T. Jajcayová, F. Mráz, D. Pardubská, M. Plátek ceedings, CEUR-WS.org, 2020, pp. 51–58. URL: http: (Eds.), Proceedings of the 22nd Conference Infor//ceur-ws.org/Vol-2718/paper13.pdf . mation Technologies – Applications and Theory [2] M. Plátek, F. Mráz, D. Pardubská, D. Průša, J. Šíma, (ITAT 2022), volume 3226 of CEUR Workshop ProOn separations of LR(0)-grammars by two types ceedings, CEUR-WS.org, 2022, pp. 130–141. URL: https://ceur-ws.org/Vol-3226/paper15.pdf .
The research has been supported by grant 1/0601/20 of the Slovak Scientific Grant Agency VEGA (Dana Pardubská) and by grant 19-21198S of the Czech Science Foundation (Daniel Průša).