We study pumping analysis by reduction represented by complete CF(c|,$)-grammars and their languages. A complete CF(c|,$)-grammar generates both a language and its complement. Complete CF(c|,$)-grammars serve as a tool to study the class of context-free languages that are closed under complement. Recall that the class of context-free grammars is the single class of languages from the Chomsky hierarchy that is not closed under the complement. The pumping reductions used in this paper ensure a correctness- and error-preserving pumping analysis by reduction for each word over its input alphabet. We introduce tests for each pumping reduction, which serve as tests of non-regularity for accepted and rejected languages by corresponding grammars. That can help to develop natural error localization and error recovery techniques for languages defined by complete CF( c|,$)-grammars.
rewritten. Instead, at most two continuous segments of the current word are deleted. In addition, we consider This paper is a continuation of the papers [1, 2, 3, 4], the pumping reduction analysis for languages generated inspired also by [5, 6]. We introduce and study com- by the so-called complete grammars. plete context-free grammars with sentinels, mainly their Informally, a complete grammar (with sentinels c| and pumping reductions and pumping tests. These notions $) is an extended context-free grammar (CFG) with are motivated by the linguistic method called analysis two initial nonterminals and . Such grammar has by reduction (here mentioned as reduction analysis); see a finite alphabet Σ of terminals not containing c| and $, [7, 8, 9, 10]. a finite alphabet of nonterminals, and a set of rewriting
Reduction analysis is a method for checking the cor- rules of the form → , where is a nonterminal rectness of an input word by stepwise rewriting some and is a string of terminals, nonterminals, and senpart of the current form with a shorter one until we obtain tinels c|, $. The language generated by the grammar a simple word for which we can decide its correctness is the set {c|} · Σ * · { $}. The set of words generated easily. In general, reduction analysis is nondeterministic, from the initial nonterminal called the accepting lanand in one step, we can rewrite a substring of a length guage, is a language of the form {c|} · · { $}, where limited by a constant with a shorter string. An input ⊆ Σ * , and the set of words generated from the secword is accepted if there is a sequence of reductions such ond initial nonterminal , called rejecting language, is that the final simple word is from the language. Then, exactly {c|} · (Σ * ∖ ) · { $}. intermediate words obtained during the analysis are also Pumping reduction analysis corresponds to a complete accepted. Each reduction must be error-preserving; that grammar when for each pair of terminal words , is, no word outside the target language can be rewritten such that can be reduced to , it holds that there are into a word from the language. some terminal words 1, 2, 3, 4, 5, and a nontermi
This paper focuses mainly on a restricted version of nal satisfying = 12345, = 135, and the reduction analysis called pumping reduction analysis, ⇒* 15 ⇒* 1245 ⇒* 12345, which has several additional properties. In each step of where equals or . Additionally, there exists a the pumping reduction analysis, the current word is not constant that depends only on grammar , such that each word of length at least can be reduced to a shorter IbTeArT2’02–42:4I,n2fo0r2m4,aDtiroinenTieccah,nSololovgaikesia– Applications and Theory, Septem- word. * Corresponding author. In general, it is undecidable whether an arbitrary con$ martin.platek@mf.cuni.cz (M. Plátek); text-free grammar generates a regular language [11]. frantisek.mraz@mf.cuni.cz (F. Mráz); This means that no algorithm can universally determine pardubska@dcs.fmph.uniba.sk (D. Pardubská); if a given CFG produces a regular language. We propose mar0t0p0r0o-c0@00g3m-3a1i4l.7c-o6m442(M( M.P.rPolcáhteákz)k;a0)000-0001-3869-3340 (F. Mráz); to use some tests to test the non-regularity of accepting 0000-0001-9383-8117 (D. Pardubská) and rejecting languages. The main result of the paper © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License says that if a complete grammar (with sentinels c| and $) CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) 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.
Definition 1 (CF( ¢,$)-grammars). Let and Σ be two disjoint alphabets, c|, $ ∈/ ( ∪ Σ) and = (, Σ ∪ {c|, $}, , ) be a context-free grammar generating a language of the form {c|} · · { $}, where ⊆ Σ * , and does not occur in the right-hand side of any rule in . We say that is a CF(c|,$)-grammar. The language is the internal language of , and is denoted in().
guages imply that for a CF(c|,$)-grammar , both languages () and in() are context-free. The added right sentinel $ facilitates the recognition of languages. E.g., if is a deterministic context-free language, then it can be generated by an LR(1)-grammar. But then, · { $} and {c|} · · { $} are both generated by simpler LR(0) grammars. The left sentinel c| is included in CF(c|,$)grammars for compatibility with RP-automata. The class of all in() characterizes the class CFL.
Definition 2. Let = (, Σ ∪ {c|, $}, , ) be a CF(c|,$)-grammar, , 1, , 2, be words over Σ , |12| > 0, and ∈ be a nonterminal. If ⇒* c|$ ⇒* c|12$ ⇒* c|12$ (1)
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 .
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 .
Definition 3. Let = (, Σ ∪ {c|, $}, , ) be a CF(c|,$)-grammar. Then is called a complete CF(c|,$)grammar if 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|} · Σ * · { $}. we say that (c|, 1, , , 2, $) is a pumping infix by , and that c|12$ ⇝ () 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|12$ ⇝ () c|$ is a two-side pumping reduc- We will denote the grammar as = (, ). Further, tion by . we will call and as accepting and rejecting gram
If 1 = we say that (c|, 1, , , 2, $) is a right- mar of the complete CF(c|,$)-grammar , respectively. side pumping infix by , and c|2$ ⇝ () c|$ is a right-side pumping reduction by . For each word of the form c|$, where ∈ Σ * , there
If 2 = we say that (c|, 1, , , 2, $) is a left- is some derivation tree according to . The node side pumping infix by , and c|1$ ⇝ () c|$ is under the root of is labeled either or . If it is a left-side pumping reduction by . , the word is generated by the accepting grammar .
The relation ⇝ * () is the reflexive and transitive closure Otherwise, it is generated by the rejecting grammar . of the pumping reduction relation ⇝ (). Moreover, for each word, two or more derivation trees can exist, but all of them are accepting or all of them are rejecting.
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.
Clearly, grammar generates the language () = {c|}· · $, where = { | ≥ ≥ 0} and grammar generates the language () = {c|} · · $, where = {, }* ∖ .
As we have the following derivation according to ⇒ ⇒ c|$ ⇒ c|$ ⇒ c|$ ⇒ c|$ ⇒ c|$ ⇒ c|$, the pumping infix (c|, , , , , $) is a pumping infix by and by . On the other hand, (c|, , , , $) Definition 4 (Pure pumping infix/reduction). Let is a pure pumping infix by and by such that there does not exist any pumping infix by of the form plete =CF((c|,$),-gra)mm=ar(,,,Σ 1∪, {,c|,$2},,b,es)ombeeawcoormds-, (c|, , , , , $), where is a nonterminal of grammar ∈ {c|} · Σ * , 1, 2 ∈ Σ * , |12| > 0, ∈ Σ * · { $}. .
• If 12 is in (), for each integer ≥ 0, we say that (, 1, , 2, ) is a pure pumping inifx by . We say that the pair of words 12, is pure pumping reduction by and write 12 ≡ > . • If 12 is in (), for each integer ≥ 0, we say that (, 1, , 2, ) is a pure pumping inifx by . We say that the pair of words 12, is pure pumping reduction by . We write 12 ≡ > .
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 12, is a pure pumping reduction by if it is a pumping reduction by or by . We write 12 ≡ > .
respond 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|$, | , | | | .
Theorem 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 ∈ Σ * , and ∈ Σ * · { $}): (ARl) The words 1 and 2 are nonempty, (, 1, , 2, ) is a pure pumping infix by , and there are integers ≥ 0, > 0 such that
Then () and () are non-regular languages. 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, 1+· 2, . . . , 1+· (+1)}︁. Obviously, there are 1 ≤ 1 < 2 ≤ +1 for each > 0, ≥ 0. (RAr’) There exists = 12 ∈ () 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.
Proof: We prove the case (ARl), whose name comes from (ARr’) There exists = 12 ∈ () such that Accept-Reject-left with the meaning that the words of the 1 and 2 are nonempty, (, 1, , , 2, ) is a form , 12 are generated by the accepting grammar pure pumping infix by , and there are integers and the words of the form 1· 1+· 2+· ≥ 0, > 0 such that are generated by the rejecting grammar , and they 1+· 2+· 2· ∈ (), contain more copies of 1 on the left from than the number of copies of 2 to the right from . Then, the for each > 0, ≥ 0. cases (ARr) (Accept-Reject-right), (RAl) (Reject-Acceptleft), and (RAr) (Reject-Accept-right) can be shown anal- (RAl’) There exists = 12 ∈ () such that ogously. 1 and 2 are nonempty, (, 1, , , 2, ) is a
Let = 12 ∈ (), where 1 and 2 are pure pumping infix by , and there are integers non-empty, (, 1, , 2, ) be a pure pumping infix by ≥ 0, > 0 such that , and ≥ 0, > 0 be integers such that Then () and () are not regular languages. such that 1+· 1 and 1+· 2 belong to the same equivalence class of the equivalence ≡ . By appending 2+· 1 to 1+· 1 , we obtain 1+· 1 2+· 1 ∈
Any of the conditions (ARl), (ARr), (RAl), (RAr), (ARl’), (ARr’), (RAl’), and (RAr’) is suficient for non-regularity of (), since (, 1, , 2, ) is a pure pumping infix a complete CF(c|,$)-grammar. Now, we examine whether by . On the other hand, 2 = 1 + 1 for some the previous suficient conditions for non-regularity are 1 > 0. According to condition (ARl), by append- also necessary for non-regularity. We start with the defing the same word 2+· 1 to 1+· 2 , we obtain inition of pumping test sets and a rather technical defithat 1+· 2 2+· 1 = 1· 1 1+· 1 2+· 1 is nition of preserving and switching tests. Based on these in (). Thus, 1+· 1 and 1+· 2 cannot be in notions, we get another condition for non-regularity in the same equivalence class . This contradiction im- Theorem 2. plies that the language () is not regular. Since the If we know that (, 1, , 2, ) is a pure pumping inclass of regular languages is closed under the comple- fix by a grammar , we have that 12 is in (), ment and intersection, the language () must also be for all integers ≥ 0. This could indicate a context-free non-regular. That finishes the proof of this case. □ dependence between the number of copies of 1 in front
As a direct consequence of Theorem 1, we get the of the factor and the number of copies of 2 after the analogous statement for (non-pure) pumping infixes. factor . However, it is still possible that all words of the form 12 belong to (). Therefore, in the Corollary 1. Let = (, ) = (, Σ ∪ {c|, $}, following, we define a switching test that should detect , ) be a complete CF(c|,$)-grammar, and at least one the situation in which there is a dependence between the of the following conditions is fulfilled (for some words number of occurrences of 1 before and the number of ∈ {c|} · Σ * , 1, , 2 ∈ Σ * , ∈ Σ * · { $}, and a non- occurrences of 2 after . terminal ∈ ): We define two types of test sets. The first one with a subscript ‘left’ should detect the situation when the (ARl’) There exists = 12 ∈ () such that number of copies of 1 can be “pumped” more times 1 and 2 are nonempty, (, 1, , , 2, ) is than the number of copies of 2. A symmetric test set a pumping infix by , and there are integers should detect the situation where the number of copies ≥ 0, > 0 such that of 2 can be “pumped” more times than the number of 1· 1+· 2+· ∈ (), copies of 1.
Let us introduce the ‘left’ test set. A pumping may require pumping several, say , copies of 1 and 2 for each > 0, ≥ 0. simultaneously in one step. Furthermore, several, say , copies of 1 and symmetrically of 2 could be produced together with the prefix and sufix , respectively.
Hence, the left test set below contains words of the form 1 1· 1· 2· 2 , for all > 0 and ≥ 0.
In order to restrict the set of pumping test sets, we require that is not greater than + 2, and is not greater than 2, where denotes the number of nonterminals of .
Definition 5 (Pumping test set).
Let = (, ) be a complete CF(c|, $)-grammar with nonterminals. Let = (, 1, , 2, ), where |1| > 0, |2| > 0, be a pure pumping infix by and , be integers such that ≤ + 2, and 0 < ≤ 2: 1. The set left(, , ) = {︀ 1 1· 1· 2· 2 |
> 0, ≥ 0︀} is called the left test set of . 2. The set right(, , ) = {︀ 1 1· 2· 2· 2
| > 0, ≥ 0 } is called the right test set of .
We say that the triple
( , , , ) = [, left(, , ), right(, , )] is a pumping test set by .
Definition 6 (Preserving/switching test set). Let = (, ) be a complete CF(c|, $)-grammar with nonterminals, = (, 1, , 2, ), where |1| > 0, |2| > 0, be a pure pumping infix by , and , be integers such that ≤ + 2 and 0 < ≤ 2.
We say that the pumping test set = ( , , , ) = [, left(, , ), right(, , )] is preserving if (Aaa) 12 ∈ () and both sets left(, , ) and
right(, , ) are subsets of (); or (Rrr) 12 ∈ () and both sets left(, , ) and
right(, , ) are subsets of ().
We say that is switching if one of the following two cases is true: (AR) 12 ∈ () and [ left(, , ) ⊆ ()
or right(, , ) ⊆ () ], (RA) 12 ∈ () and [ left(, , ) ⊆ () or right(, , ) ⊆ () ].
Theorem 2. Let = (, ) be a complete CF(c|, $)-grammar, and suppose there exists a switching pumping test set by . Then (), and () are non-regular languages.
regular languages when the condition (AR) holds. The other cases can be shown similarly.
Let = (, ) be a complete CF(c|,$)-grammar with nonterminals, = (, 1, , 2, ), where |1| > 0, |2| > 0, be a pure pumping infix by and , be integers such that ≤ + 2 and 0 < ≤ 2, and
= ( , , , ) = [, left(, , ), right(, , )] be a switching pumping test set such that 12 ∈ () and at least one of the following conditions is true: 1. left(, , ) ⊆ (), or 2. right(, , ) ⊆ ().
As 12 ∈ () and = (, 1, , 2, ) is a pure pumping infix by , is a pure pumping infix by .
In case 1, the condition (ARl) of Theorem 1 is satisfied. Hence, according to Theorem 1, both languages () and () are not regular.
In case 2, the condition (ARr) of Theorem 1 is satisfied. Hence, according to Theorem 1, both languages () and () are not regular.
Similarly, we can show the case where the condition (RA) holds. □
to compare regularity and non-regularity connected with complete CF(c|, $)-grammars. This section gives a partial idea of our plans for the future. In general, we will try to solve the decidability questions connected with (non)regularity of complete CF(c|, $)-grammars.
Test languages. Let = (, ) be a complete CF(c|, $)-grammar. Let 1 and 2 be nonempty words, and = (, 1, , 2, ) be a pure pumping infix by .
We say that the languages () ∩ {12 | , ≥ 0} and () ∩ {12 | , ≥ 0}
The following theorem is a direct consequence of The- are test languages of . We also say that the languages orem 1 and the definition of the switching pumping test are test languages of . set. Concerning the test languages, we have several conjectures.
Conjecture 3. Let = (, ) be a complete CF(c|, $)-grammar. Then () and () are regular if and only if all test languages of are regular.
preserving test give an opportunity to introduce degrees of regularity and degrees for non-regularity of complete CF(c|, $)-grammars. That will also be one direction of our eforts in the future.
Conjecture 2. Let = (, ) be a complete CF(c|, $)-grammar, and there does not exist any switching pumping test by . Then, each test language of is regular.
CEUR Workshop Proceedings, CEUR-WS.org, 2023, pp. 110–120. URL: https://ceur-ws.org/Vol-3498/ paper14.pdf . [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, August 23–27, 2021, Tallinn, Estonia, 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] 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 2019, Sydney, NSW, Australia, December 12–15, 2019, 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. [7] M. Lopatková, M. Plátek, P. Sgall, Towards a formal [1] F. Mráz, D. Pardubská, M. Plátek, J. Šíma, Pump- model for functional generative description: Analing deterministic monotone restarting automata ysis by reduction and restarting automata, Prague and DCFL, in: M. Holeňa, T. Horváth, A. Kele- Bull. Math. Linguistics 87 (2007) 7–26. URL: http: menová, F. Mráz, D. Pardubská, M. Plátek, P. Sosík //ufal.mf.cuni.cz/pbml/87/lopatkova-et-al.pdf . (Eds.), Proceedings of the 20th Conference Infor- [8] P. Jančar, F. Mráz, M. Plátek, J. Vogel, Restarting mation Technologies – Applications and Theory automata, in: H. Reichel (Ed.), Fundamentals of (ITAT 2020), volume 2718 of CEUR Workshop Pro- Computation Theory, FCT ’95, volume 965 of Lecceedings, CEUR-WS.org, 2020, pp. 51–58. URL: http: ture Notes in Computer Science, Springer, 1995, pp. //ceur-ws.org/Vol-2718/paper13.pdf . 283–292. doi:10.1007/3-540-60249-6_60. [2] M. Plátek, F. Mráz, D. Pardubská, D. Průša, J. Šíma, [9] P. Jančar, F. Mráz, M. Plátek, J. Vogel, On monoOn separations of LR(0)-grammars by two types tonic automata with a restart operation, J. Auof pumping patterns, in: B. Brejová, L. Cien- tom. Lang. Comb. 4 (1999) 287–311. doi:10.25596/ cialová, M. Holeňa, F. Mráz, D. Pardubská, M. Plátek, jalc-1999-287.
T. Vinař (Eds.), Proceedings of the 21st Conference [10] F. Otto, Restarting automata, in: Z. Ésik, Information Technologies – Applications and The- C. Martín-Vide, V. Mitrana (Eds.), Recent Adory (ITAT 2021), volume 2962 of CEUR Workshop vances in Formal Languages and Applications, Proceedings, CEUR-WS.org, 2021, pp. 140–146. URL: volume 25 of Studies in Computational Intellihttp://ceur-ws.org/Vol-2962/paper05.pdf . gence, Springer, 2006, pp. 269–303. URL: https://doi. [3] M. Plátek, F. Mráz, D. Pardubská, D. Průša, On org/10.1007/978-3-540-33461-3_11. doi:10.1007/ pumping RP-automata controlled by complete 978-3-540-33461-3_11.
LRG(¢, $)-grammars, in: L. Ciencialová, M. Holeňa, [11] J. O. Shallit, A Second Course in Formal Languages R. Jajcay, T. Jajcayová, F. Mráz, D. Pardubská, and Automata Theory, Cambridge University Press, M. Plátek (Eds.), Proceedings of the 22nd Confer- 2008. ence Information Technologies – Applications and [12] J. Hopcroft, J. Ullman, Introduction to Automata Theory (ITAT 2022), volume 3226 of CEUR Work- Theory, Languages, and Computation, Addisonshop Proceedings, CEUR-WS.org, 2022, pp. 111–121. Wesley, N. Reading, MA, 1980.
URL: https://ceur-ws.org/Vol-3226/paper13.pdf . [4] F. Mráz, M. Plátek, D. Pardubská, D. Průša, Oneside pumping and two-side pumping by complete CF(¢, $)-grammars, in: B. Brejová, L. Ciencialová,