Introduction

This paper is a continuation of the papers [1,2,3,4], inspired also by [5,6]. We introduce and study complete context-free grammars with sentinels, mainly their pumping reductions and pumping tests. These notions are motivated by the linguistic method called analysis by reduction (here mentioned as reduction analysis); see [7,8,9,10].

Reduction analysis is a method for checking the correctness of an input word by stepwise rewriting some part of the current form with a shorter one until we obtain a simple word for which we can decide its correctness easily. In general, reduction analysis is nondeterministic, and in one step, we can rewrite a substring 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 language. Then, intermediate words obtained during the analysis are also accepted. Each reduction must be error-preserving; that is, no word outside the target language can be rewritten into a word from the language.

This paper focuses mainly on a restricted version of the reduction analysis called pumping reduction analysis, which has several additional properties. In each step of the pumping reduction analysis, the current word is not rewritten. Instead, at most two continuous segments of the current word are deleted. In addition, we consider the pumping reduction analysis for languages generated by the so-called complete grammars.

Informally, a complete grammar (with sentinels | c and $) 𝐺𝐶 is an extended context-free grammar (CFG) with two initial nonterminals 𝑆𝐴 and 𝑆𝑅. Such grammar has a finite alphabet Σ of terminals not containing | c and $, a finite alphabet of nonterminals, and a set of rewriting rules of the form 𝑋 → 𝛼, where 𝑋 is a nonterminal and 𝛼 is a string of terminals, nonterminals, and sentinels | c, $. The language generated by the grammar is the set

{ | c} • Σ * • {$}.

The set of words generated from the initial nonterminal 𝑆𝐴 called the accepting language, is a language of the form { | c} • 𝐿 • {$}, where 𝐿 ⊆ Σ * , and the set of words generated from the second initial nonterminal 𝑆𝑅, called rejecting language, is exactly

{ | c} • (Σ * ∖ 𝐿) • {$}.

Pumping reduction analysis corresponds to a complete grammar 𝐺𝐶 when for each pair of terminal words 𝑢, 𝑣 such that 𝑢 can be reduced to 𝑣, it holds that there are some terminal words 𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5, and a nonterminal 𝐴 satisfying 𝑢 = 𝑥1𝑥2𝑥3𝑥4𝑥5, 𝑣 = 𝑥1𝑥3𝑥5, and

𝑆 ⇒ * 𝐺 𝐶 𝑥1𝐴𝑥5 ⇒ * 𝐺 𝐶 𝑥1𝑥2𝐴𝑥4𝑥5 ⇒ * 𝐺 𝐶 𝑥1𝑥2𝑥3𝑥4𝑥5

, where 𝑆 equals 𝑆𝐴 or 𝑆𝑅. Additionally, there exists a constant 𝑐 that depends only on grammar 𝐺𝐶 , such that each word of length at least 𝑐 can be reduced to a shorter word.

In general, it is undecidable whether an arbitrary context-free grammar generates a regular language [11]. This means that no algorithm can universally determine if a given CFG produces a regular language. We propose to use some tests to test the non-regularity of accepting and rejecting languages. The main result of the paper says that if a complete grammar (with sentinels | c and $)

𝐺𝐶 has a switching pumping test, then its accepting and rejecting languages are non-regular. This paper is structured as follows. Section 2 introduces CF( | c,$)-grammars, pumping infixes and reductions, and complete CF( | c,$)-grammars. Section 3 presents the main result. It is followed by a section that discusses open problems and future work.

Basic notions

Pumping infixes and reductions𝑆 ⇒ * | c𝑥𝐴𝑦$ ⇒ * | c𝑥𝑢1𝐴𝑢2𝑦$ ⇒ * | c𝑥𝑢1𝑣𝑢2𝑦$ (1)

we say that ( | c𝑥, 𝑢1, 𝐴, 𝑣, 𝑢2, 𝑦$) is a pumping infix by 𝐺, and that | c𝑥𝑢1𝑣𝑢2𝑦$ ⇝ 𝑃 (𝐺) | c𝑥𝑣𝑦$ is a pumping reduction by 𝐺.

If both 𝑢1 and 𝑢2 are not empty, we say that ( | c𝑥, 𝑢1, 𝐴, 𝑣, 𝑢2, 𝑦$) is a two-side pumping infix by 𝐺, and that

| c𝑥𝑢1𝑣𝑢2𝑦$ ⇝ 𝑃 (𝐺) | c𝑥𝑣𝑦$ is a two-side pumping reduc- tion by 𝐺. If 𝑢1 = 𝜆 we say that ( | c𝑥, 𝑢1, 𝐴, 𝑣, 𝑢2, 𝑦$) is a right- side pumping infix by 𝐺, and | c𝑥𝑣𝑢2𝑦$ ⇝ 𝑃 (𝐺) | c𝑥𝑣𝑦$ is a right-side pumping reduction by 𝐺. If 𝑢2 = 𝜆 we say that ( | c𝑥, 𝑢1, 𝐴, 𝑣, 𝑢2, 𝑦$) is a left- side pumping infix by 𝐺, and | c𝑥𝑢1𝑣𝑦$ ⇝ 𝑃 (𝐺) | c𝑥𝑣𝑦$ is a left-side pumping reduction by 𝐺.

The relation ⇝ * 𝑃 (𝐺) is the reflexive and transitive closure of the pumping reduction relation ⇝ 𝑃 (𝐺) .

Note that we have not omitted the sentinels in the pumping infix and pumping reduction.

If ( | c𝑥, 𝑢1, 𝐴, 𝑣, 𝑢2, 𝑦$) is a pumping infix by 𝐺, then all words of the form | c𝑥𝑢 𝑖 1 𝑣𝑢 𝑖 2 𝑦$, for all integers 𝑖 ≥ 0, belong to 𝐿(𝐺).

Let 𝐺 = (𝑁, Σ ∪ { | c, $}, 𝑆, 𝑅) be a CF( | c,$)-grammar, 𝑡 be the number of nonterminals of 𝐺, and 𝑘 be the maximal length of the right-hand side of the rules in 𝑅. Let 𝑇 be a derivation tree according to 𝐺. If 𝑇 has more than 𝑘 𝑡 leaves, a path exists from a leaf to the root of 𝑇 such that it contains at least 𝑡 + 1 nodes labeled by nonterminals. As 𝐺 has only 𝑡 nonterminals, at least two nodes on the path are labeled with the same nonterminal 𝐴. In that case, there is a pumping reduction corresponding to this word. We say that 𝐾𝐺 = 𝑘 𝑡 is the grammar number of 𝐺.

Note that for each word from 𝐿(𝐺) of length greater than 𝐾𝐺, some pumping infix by 𝐺 must correspond. On the other hand, each word generated by 𝐺 that is not pumped is of length at most 𝐾𝐺.

Note that in the above derivation (1), the length of the words 𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦 is not limited.

A pumping reduction 𝑤 ⇝ 𝑃 (𝐺) 𝑤 ′ corresponds to removing a part of the derivation tree between some two nodes 𝑟1, 𝑟2 labeled with the same nonterminal 𝐴 occurring on a path from the root of the derivation tree for 𝑤.

Complete CF(¢,$)-grammarsDefinition 3. Let 𝐺𝐶 = (𝑁, Σ ∪ { | c, $}, 𝑆, 𝑅) be a CF( | c,$)-grammar. Then 𝐺𝐶 is called a complete CF( | c,$)- grammar if 1. 𝑆 → 𝑆𝐴 | 𝑆𝑅,{ | c} • Σ * • {$}. That is, 𝐿(𝐺𝐴) ∩ 𝐿(𝐺𝑅) = ∅ and 𝐿(𝐺𝐶 ) = 𝐿(𝐺𝐴) ∪ 𝐿(𝐺𝑅) = { | c} • Σ * • {$}.

We will denote the grammar as 𝐺𝐶 = (𝐺𝐴, 𝐺𝑅). Further, we will call 𝐺𝐴 and 𝐺𝑅 as accepting and rejecting grammar of the complete CF( | c,$)-grammar 𝐺𝐶 , respectively.

For each word of the form | c𝑤$, where 𝑤 ∈ Σ * , there is some derivation tree 𝑇 according to 𝐺𝐶 . The node under the root of 𝑇 is labeled either 𝑆𝐴 or 𝑆𝑅. If it is 𝑆𝐴, the word is generated by the accepting grammar 𝐺𝐴. Otherwise, it is generated by the rejecting grammar 𝐺𝑅.

Moreover, for each word, two or more derivation trees can exist, but all of them are accepting or all of them are rejecting.

Non-regularity by complete CF(¢,$)-grammars

If 𝐺𝐶 is a complete CF( | c,$)-grammar, then both 𝐿(𝐺𝐴) and 𝐿(𝐺𝑅) are context-free languages. How can we decide whether those languages are regular or non-regular? In this section, we show some properties that help answer that question.

At first, we introduce a weaker notion of pumping infix that does not contain the information on which nonterminal is pumped.

Definition 4 (Pure pumping infix/reduction). Let𝐺𝐶 = (𝐺𝐴, 𝐺𝑅) = (𝑁, Σ ∪ { | c, $}, 𝑆, 𝑅) be a com- plete CF( | c, $)-grammar, 𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦 be some words, 𝑥 ∈ { | c} • Σ * , 𝑢1, 𝑢2 ∈ Σ * , |𝑢1𝑢2| > 0, 𝑦 ∈ Σ * • {$}. • If 𝑥𝑢 𝑛 1 𝑣𝑢 𝑛 2 𝑦 is in 𝐿(𝐺𝐴)

, for each integer 𝑛 ≥ 0, we say that (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝐴. We say that the pair of words 𝑥𝑢1𝑣𝑢2𝑦, 𝑥𝑣𝑦 is pure pumping reduction by 𝐺𝐴 and write 𝑥𝑢1𝑣𝑢2𝑦 ≡>𝐺 𝐴 𝑥𝑣𝑦.

• If 𝑥𝑢 𝑛 1 𝑣𝑢 𝑛 2 𝑦 is in 𝐿(𝐺𝑅)

, for each integer 𝑛 ≥ 0, we say that (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝑅. We say that the pair of words 𝑥𝑢1𝑣𝑢2𝑦, 𝑥𝑣𝑦 is pure pumping reduction by 𝐺𝑅. We write 𝑥𝑢1𝑣𝑢2𝑦 ≡>𝐺 𝑅 𝑥𝑣𝑦.

We say that (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝐶 if it is a pure pumping infix by 𝐺𝐴 or by 𝐺𝑅. We say that the pair of words 𝑥𝑢1𝑣𝑢2𝑦, 𝑥𝑣𝑦 is a pure pumping reduction by 𝐺𝐶 if it is a pumping reduction by 𝐺𝐴 or by 𝐺𝑅. We write 𝑥𝑢1𝑣𝑢2𝑦 ≡>𝐺 𝐶 𝑥𝑣𝑦.

Actually, pure pumping infix need not directly correspond to any pumping infix by the given complete CF( | c,$)-grammar. This is illustrated with the following example.

Example 1. Let 𝐺𝐶 = (𝐺𝐴, 𝐺𝑅), 𝐺𝐶 = (𝑁, Σ ∪ { | c, $}, 𝑆, 𝑅) be a complete CF( | c,$)-grammar, where 𝑁 = {𝑆, 𝑆𝐴, 𝑆𝑅, 𝐴, 𝐵, 𝐶, 𝐷, 𝐸}, Σ = {𝑎, 𝑏}, 𝑆𝐴 and 𝑆𝑅 are the initial nonterminals of the grammars 𝐺𝐴 and 𝐺𝑅, respectively, and 𝑅 consists of the following rules:

𝑆 → 𝑆𝐴 | 𝑆𝑅, 𝑆𝐴 → | c$ | | c𝐴$ | | c𝐴𝐶$ | | c𝐶$, 𝐴 → 𝑎𝐴 | 𝑎, 𝐶 → 𝑎𝐷𝑏 | 𝑎𝑏, 𝐷 → 𝑎𝐶𝑏 | 𝑎𝑏, 𝑆𝑅 → | c𝐵$ | | c𝐶𝐵$ | | c𝑏𝑎$ | | c𝐸𝑎𝑏$ | | c𝑎𝑏𝐸$ | | c𝐸𝑎𝑏$, 𝐵 → 𝑏𝐵 | 𝑏, 𝐸 → 𝑎𝐸 | 𝑏𝐸 | 𝑎 | 𝑏.

Clearly

𝑥𝑢 𝑗•𝑚 1 𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑦 ∈ 𝐿(𝐺𝑅),

for each 𝑚 > 0, 𝑛 ≥ 0.

(ARr) There exists 𝑤 = 𝑥𝑢1𝑣𝑢2𝑦 ∈ 𝐿(𝐺𝐴) such that 𝑢1 and 𝑢2 are nonempty, (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝐴, and there are integers 𝑖 ≥ 0, 𝑗 > 0 such that

𝑥𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑢 𝑗•𝑚 2 𝑦 ∈ 𝐿(𝐺𝑅),

for each 𝑚 > 0, 𝑛 ≥ 0.

(RAl) There exists 𝑤 = 𝑥𝑢1𝑣𝑢2𝑦 ∈ 𝐿(𝐺𝑅) such that 𝑢1 and 𝑢2 are nonempty, (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝑅, and there are integers 𝑖 ≥ 0, 𝑗 > 0 such that

𝑥𝑢 𝑗•𝑚 1 𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑦 ∈ 𝐿(𝐺𝐴),

for each 𝑚 > 0, 𝑛 ≥ 0.

(RAr) There exists 𝑤 = 𝑥𝑢1𝑣𝑢2𝑦 ∈ 𝐿(𝐺𝑅) such that 𝑢1 and 𝑢2 are nonempty, (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝑅, and there are integers 𝑖 ≥ 0, 𝑗 > 0 such that

𝑥𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑢 𝑗•𝑚 2 𝑦 ∈ 𝐿(𝐺𝐴),

for each 𝑚 > 0, 𝑛 ≥ 0.

Then 𝐿(𝐺𝐴) and 𝐿(𝐺𝑅) are non-regular languages.

Proof: We prove the case (ARl), whose name comes from Accept-Reject-left with the meaning that the words of the form 𝑥, 𝑢 𝑟 1 𝑣𝑢 𝑟 2 𝑦 are generated by the accepting grammar 𝐺𝐴 and the words of the form

𝑥𝑢 𝑗•𝑚 1 𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑦

are generated by the rejecting grammar 𝐺𝑅, and they contain more copies of 𝑢1 on the left from 𝑣 than the number of copies of 𝑢2 to the right from 𝑣. Then, the cases (ARr) (Accept-Reject-right), (RAl) (Reject-Acceptleft), and (RAr) (Reject-Accept-right) can be shown analogously.

Let 𝑤 = 𝑥𝑢1𝑣𝑢2𝑦 ∈ 𝐿(𝐺𝐴), where 𝑢1 and 𝑢2 are non-empty, (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) be a pure pumping infix by 𝐺𝐴, and 𝑖 ≥ 0, 𝑗 > 0 be integers such that

𝑥𝑢 𝑗•𝑚 1 𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑦 ∈ 𝐿(𝐺𝑅),

for each 𝑚 > 0, 𝑛 ≥ 0.

Assume for a contradiction that 𝐿(𝐺𝐴) and 𝐿(𝐺𝑅) are regular languages. According to Myhill-Nerode Theorem [12], a right congruence ≡ with a finite index 𝑟 exists such that language 𝐿(𝐺𝐴) is a union of some of its equivalence classes.

Consider the set of words

{︁ 𝑥𝑢 𝑖+𝑗•1 1 , 𝑥𝑢 𝑖+𝑗•2 1 , . . . , 𝑥𝑢 𝑖+𝑗•(𝑟+1) 1 }︁ . Obviously, there are 1 ≤ 𝑘1 < 𝑘2 ≤ 𝑟+1 such that 𝑥𝑢 𝑖+𝑗•𝑘 1 1 and 𝑥𝑢 𝑖+𝑗•𝑘 2 1

belong to the same equivalence class 𝐶𝑙 of the equivalence ≡. By appending

𝑣𝑢 𝑖+𝑗•𝑘 1 2 𝑦 to 𝑥𝑢 𝑖+𝑗•𝑘 1 1 , we obtain 𝑥𝑢 𝑖+𝑗•𝑘 1 1 𝑣𝑢 𝑖+𝑗•𝑘 1 2

𝑦 ∈ 𝐿(𝐺𝐴), since (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝐴. On the other hand, 𝑘2 = 𝑘1 + 𝑚1 for some 𝑚1 > 0. According to condition (ARl), by appending the same word

𝑣𝑢 𝑖+𝑗•𝑘 1 2 𝑦 to 𝑥𝑢 𝑖+𝑗•𝑘 2 1 , we obtain that 𝑥𝑢 𝑖+𝑗•𝑘 2 1 𝑣𝑢 𝑖+𝑗•𝑘 1 2 𝑦 = 𝑥𝑢 𝑗•𝑚 1 1 𝑢 𝑖+𝑗•𝑘 1 1 𝑣𝑢 𝑖+𝑗•𝑘 1 2

𝑦 is in 𝐿(𝐺𝑅). Thus, 𝑥𝑢 𝑖+𝑗•𝑘 1 1 and 𝑥𝑢 𝑖+𝑗•𝑘 2 1 cannot be in the same equivalence class 𝐶𝑙. This contradiction implies that the language 𝐿(𝐺𝐴) is not regular. Since the class of regular languages is closed under the complement and intersection, the language 𝐿(𝐺𝑅) must also be non-regular. That finishes the proof of this case. □

As a direct consequence of Theorem 1, we get the analogous statement for (non-pure) pumping infixes.

Corollary 1. Let 𝐺𝐶 = (𝐺𝐴, 𝐺𝑅) = (𝑁, Σ ∪ { | c, $}, 𝑆, 𝑅) be a complete CF( | c,$)-grammar, and at least one of the following conditions is fulfilled (for some words

𝑥 ∈ { | c} • Σ * , 𝑢1, 𝑣, 𝑢2 ∈ Σ * , 𝑦 ∈ Σ * • {$},𝑥𝑢 𝑗•𝑚 1 𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑦 ∈ 𝐿(𝐺𝑅),

for each 𝑚 > 0, 𝑛 ≥ 0.

(ARr') There exists 𝑤 = 𝑥𝑢1𝑣𝑢2𝑦 ∈ 𝐿(𝐺𝐴) such that 𝑢1 and 𝑢2 are nonempty, (𝑥, 𝑢1, 𝐴, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝐴, and there are integers 𝑖 ≥ 0, 𝑗 > 0 such that

𝑥𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑢 𝑗•𝑚 2 𝑦 ∈ 𝐿(𝐺𝑅),

for each 𝑚 > 0, 𝑛 ≥ 0.

(RAl') There exists 𝑤 = 𝑥𝑢1𝑣𝑢2𝑦 ∈ 𝐿(𝐺𝑅) such that 𝑢1 and 𝑢2 are nonempty, (𝑥, 𝑢1, 𝐴, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝑅, and there are integers 𝑖 ≥ 0, 𝑗 > 0 such that

𝑥𝑢 𝑗•𝑚 1 𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑦 ∈ 𝐿(𝐺𝐴),

for each 𝑚 > 0, 𝑛 ≥ 0.

(RAr') There exists 𝑤 = 𝑥𝑢1𝑣𝑢2𝑦 ∈ 𝐿(𝐺𝑅) such that 𝑢1 and 𝑢2 are nonempty, (𝑥, 𝑢1, 𝐴, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by 𝐺𝑅, and there are integers 𝑖 ≥ 0, 𝑗 > 0 such that

𝑥𝑢 𝑖+𝑗•𝑛 1 𝑣𝑢 𝑖+𝑗•𝑛 2 𝑢 𝑗•𝑚 2 𝑦 ∈ 𝐿(𝐺𝐴),

for each 𝑚 > 0, 𝑛 ≥ 0.

Then 𝐿(𝐺𝐴) and 𝐿(𝐺𝑅) are not regular languages.

Any of the conditions (ARl), (ARr), (RAl), (RAr), (ARl'), (ARr'), (RAl'), and (RAr') is sufficient for non-regularity of a complete CF( | c,$)-grammar. Now, we examine whether the previous sufficient conditions for non-regularity are also necessary for non-regularity. We start with the definition of pumping test sets and a rather technical definition of preserving and switching tests. Based on these notions, we get another condition for non-regularity in Theorem 2.

If we know that (𝑥, 𝑢1, 𝑣, 𝑢2, 𝑦) is a pure pumping infix by a grammar 𝐺𝐴, we have that 𝑥𝑢 𝑟 1 𝑣𝑢 𝑟 2 𝑦 is in 𝐿(𝐺𝐴), for all integers 𝑟 ≥ 0. This could indicate a context-free dependence between the number of copies of 𝑢1 in front of the factor 𝑣 and the number of copies of 𝑢2 after the factor 𝑣. However, it is still possible that all words of the form 𝑥𝑢 𝑚 1 𝑣𝑢 𝑛 2 𝑦 belong to 𝐿(𝐺𝐴). Therefore, in the following, we define a switching test that should detect the situation in which there is a dependence between the number of occurrences of 𝑢1 before and the number of occurrences of 𝑢2 after 𝑣.

We define two types of test sets. The first one with a subscript 'left' should detect the situation when the number of copies of 𝑢1 can be "pumped" more times than the number of copies of 𝑢2. A symmetric test set should detect the situation where the number of copies of 𝑢2 can be "pumped" more times than the number of copies of 𝑢1.

Let us introduce the 'left' test set. A pumping may require pumping several, say 𝑗, copies of 𝑢1 and 𝑢2