Complete CF(¢,$)-grammar inspired by linguistic techniques can serve as a tool for studying the class of contextfree languages that are closed under complement. Such grammar generates a complementary pair of context-free languages. Here, we introduce a restricted version of complete CF(¢,$)-grammars called PS-free pumping CF(¢,$)grammars, which satisfy restrictions that extend the conditions of the pumping lemma for regular languages. PS-free pumping CF(¢,$)-grammars generate regular languages only. However, the conditions put on PS-free pumping CF(¢,$)-grammars are suficient but not necessary for regularity.
∗Corresponding author.
CEUR Workshop
ISSN1613-0073 reductions in the prefix and sufix of a word. We show that each PS-free pumping CF( c|,$)-grammar induces a language equivalence relation with finite index such that the acceptance language of is one of the equivalence classes. Then, by applying Myhill-Nerode theorem [5, Theorem 3.1], we get that both acceptance and rejection languages of are regular.
The next section defines the basic notions, introduces complete CF( c|,$)-grammars, and reviews their known properties. Section 3 introduces PS-free pumping grammars and proves the main result of the paper stating that each PS-free pumping grammar has regular acceptance and rejection languages. Section 4 shows examples that PS-free pumping grammar need not be one-sided (informally, its pumping reductions can remove only one segment of a word in one simplification step), and that a complete grammar generating a regular language need not be PS-free pumping. The last section contains conclusions and an outlook for future research.
An alphabet is an arbitrary finite set of elements called symbols. A word over the alphabet Σ is a ifnite sequence of symbols from Σ. The set of all words over the alphabet Σ is denoted as Σ∗. If and are words, or ⋅ denotes their concatenation. By | | we denote the length of the word, that is, the number of symbols in . The length of the empty word is 0.
A context-free grammar is a system = ( , Σ, , ) , where is an alphabet of nonterminals, Σ is an alphabet of input symbols called terminals ( ∩ Σ = ∅ ), ∈ is an initial nonterminal, and is a finite subset of × ( ∪ Σ) ∗, is called a set of rules and its elements are written in the form → , where ∈ and ∈ ( ∪ Σ) ∗.
We say that a word ∈ ( ∪ Σ) ∗ can be rewritten into a word ∈ ( ∪ Σ) ∗ according to contextfree grammar = ( , Σ, , ) if there exist words 1, 2, ∈ ( ∪ Σ) ∗ and a nonterminal ∈ such that = 1 2, = 1 2, and → is a rule from . We write ⇒ . The reflexive and transitive closure of the relation ⇒ is denoted as ⇒∗. Then the language generated by the grammar is () = { ∈ Σ ∗ ∣ ⇒ ∗ } .
Definition 1 (CF( c|,$)-grammars, [6]). 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 from . We say that is a CF( c|,$)-grammar. The language is the internal language of , and it is denoted as in() .
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 right sentinel $ facilitates the recognition
of languages. For example, if is a deterministic context-free language, it can be generated by an
LR(
Definition 2 ([6]). Let = ( , Σ ∪ { and We say that ( c|, 1, , , .
The infix and the reduction are two-side if both 1 and 2 are nonempty. They are right-side ( left-side , respectively) if 1 ( 2, respectively) is empty.
The relation ∗ is the reflexive and transitive closure of the pumping reduction relation .
be a CF( c|,$)-grammar, , 1, , 2, ∈ Σ ∗, 1 2 ≠ , ∈ ,
⇒ ∗ c| $ ⇒
∗ c| 1 2 $ ⇒ ∗ c| 1 2 $.
(
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 from , where the sentinels c|, $ are not counted. Let be a derivation tree according to . If has more than leaves from Σ, a path exists from a leaf to the root of such that it contains at least + 1 nodes labeled with 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 = + 2 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 at most of length . In the following, we will separate words that can be pumped from those that cannot.
Note that in the above derivation (
A pumping reduction ′ corresponds to removing a segment between any nodes 1 and 2 labeled with the same nonterminal occurring on a path from the root of a derivation tree for .
The following obvious propositions were proved in [3].
Proposition 1 (Pumping reductions are correctness preserving, [3]). Let = ( , Σ ∪ { c|, $}, , ) be a CF( c|,$)-grammar. Let generate a word 1, and 1, … , , for some integer ≥ 1 , be a sequence of words such that +1 , for all = 1, … , − 1 , be a sequence of pumping reductions, and there is no +1 ∈ Σ∗ such that +1 .
Then ∈ () , for all = 1, … , and | | ≤ .
Proposition 2 ([3]). Let = ( , Σ ∪ { c|, $}, , ) be a CF( c|,$)-grammar, and generates a word 1 (that is, 1 ∈ () ), and | 1| > . Then there is a sequence of words 1, … , , for some integer ≥ 1 such that, for all = 1, … , − 1 , +1 , ∈ () , for all = 1, … , , and | | ≤ .
In contrast to previous definitions (e.g., [ 3]), the following definition of complete CF( c|,$)-grammar requires that such a grammar to be reduced – it does not contain useless nonterminals (with a minor exception).
Definition 3. Let = ( , Σ ∪ { c|, $}, , ) grammar if
be a CF( c|,$)-grammar. Then is called a complete CF( c|,$)1. → ∣ , where , ∈ , are the only rules in containing the initial nonterminal . No other rule of contains or in its right-hand 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|} ⋅ Σ∗ ⋅ {$}. 3. All nonterminals of can be derived from , and from all nonterminals of (except for and ) there are derivations of terminal words.
We will denote the grammar as = ( , ). In addition, we will call and the acceptance and rejection grammar of the complete CF( c|,$)-grammar , respectively.
The above definition implies that for each word of the form c| $ , where ∈ Σ ∗, there is some derivation tree according to . The root of has a single son labeled with one of the nonterminals and . If it is , the word from the leaves of the tree is from ( ), otherwise it is from ( ).
For any terminal word ∈ { c|} ⋅ Σ∗ ⋅ {$}, there can exist several derivation trees. However, if ∈ ( ), all have under their root. If ∈ ( ), they will have under their root.
As ( ) = { c|} ⋅ Σ∗ ⋅ {$} is an infinite language, there exist pumping reductions by ([6]).
The condition that both acceptance and rejection grammar of a complete CF( c|,$)-grammar are context-free seems to be quite restrictive, but the class of deterministic context-free languages is closed under complement. Hence, if is a CF( c|,$)-grammar which is LR(0), then there exists a complete CF( c|,$)-grammar = ( , ) which is LR (0) (see, e.g., [8]).
In [6] it was shown that if an acceptance or rejection language of a complete CF( c|,$)-grammar = ( , ) enables pumping where two nonempty segments can be pumped and some other requirements are fulfilled, then the languages ( ) and (
) are not regular.
In the following, we will use conditions similar to those in the well-known pumping lemma for
and , are any (possibly empty) strings. It then follows that can be written in the form = where 1 ≤ || ≤ and where is in () , for all ≥ 0 .
Corollary 1. Let be a regular language, then there exists a constant > 0 such that, for all words 1, 2 such that 1 2 is in , | 1| > , 2 is any (possibly empty) word, there exists a word 1′ so that | 1′| < | 1|, of Corollary 1 follows for = 0 .
Proof: As 1 2 ∈ , we can apply Proposition 3, where = , = 1, = 2, and is the number of states of a finite-state automaton accepting the language . Then we can take 1′ = and the statement
In other words, each long enough word from can be shortened in its prefix of length at least into a shorter word from . As the class of regular languages is closed under reversal, an analogous statement also holds for sufixes of limited size. Nevertheless, it is known that Proposition 3 (and therefore also Corollary 1) is not a suficient condition for the regularity of a language. Below, we use similar conditions for prefixes and sufixes together with further independence conditions of reductions Definition 4. Let = ( , ) be a complete CF( c|, $)-grammar and > 0 be a constant such that ′
′ ′. ′ and
′. (C) For all words , , ′ and ′ such that ∈ ( (P) for each ∈ ( (S) for each ∈ ( ) such that || > , there is 1 such that ) such that || > , there is 1 such that 1 , and 1. ), || > , || > , ′ ′ ′ implies (D) For each ′, ′ ∈ ( ) such that || > , || > , ′ ′ ′ and ′ ′ ′ it holds We say that is a PS-free pumping CF( c|, $)-grammar of width .
The additional conditions (C) and (D) in Definition 4 add “independence” of reductions in prefix and sufix. We will see that all these conditions together guarantee the regularity of the languages ( ) and (
).
Recall that each pumping reduction by on ∈ ( ) is a pumping reduction by . Similarly, each pumping reduction by on ∈ (
) is a pumping reduction by .
Definition 5 (Prefix-sufix reduction)
. Let = ( , ) be a complete CF( c|, $)-grammar of width . • Let be a pumping reduction of the form
1 , and || > . We say that is a prefix reduction (P-reduction) by of width . The word is the prefix being reduced, and is the (fixed) sufix of .
Note that the length of the sufix is not limited. in the prefixes and sufixes. and ( ) are regular.
Here, we introduce a restricted version of complete CF( c|,$)-grammar that guarantees that both ( ) ′ 1 ′ 1 1 ′ ′
1, and || > . We say that is a sufix reduction (S-reduction) by of width . The word is the sufix being reduced, and is the (fixed) prefix of .
1 1, and let be either a P-reduction or an
We also say that , where || > 0 , is a PS-prefix and that , || > 0 , is a PS-sufix.
Observation Let = ( , ) be a PS-free pumping CF( c|, $)-grammar of width . Then the following assertions hold: (a1) For each ∈ ( ) such that 1 1 we have the following (a2) For each ∈ ( ) there is a reduction ∗ ( ,) 1 1 such that | 1| ≤ , | 1| ≤ . ). That is, all PS-reductions are error- and correctness-preserving.
Lemma 1. Let = ( , ) be a PS-free pumping CF( c|, $)-grammar of width . Then, for all words , , Proof: According to Definition 4, the statement holds for two-step pumping reductions. E.g., if in the reduction and the second part only one step ′ ∗ ′ ∗ ′ ′, the first part ′ ′, we have a three step reduction ∗ ′ requires two steps: 1
1 ′ ′ ′ and we can apply condition (C) to the last two steps. We get the sequence of reductions ′ ′. Next, we apply condition (C) to the first two reductions and get ′ ′. Hence, ∗ ′ ∗ ′.
Using similar reduction reordering, we can prove the statement of the lemma by induction on the number of steps in the series of reductions.
grammar of width , and be a word in ( ).
Next, we introduce PS-prefixes and PS-sufixes with a limited size.
• If 0 < || ≤ , we say that is a basic PS-prefix by of width .
• If 0 < || ≤ , we say that is a basic PS-sufix by of width .
The set of all PS-prefixes for will be denoted as The set of all basic PS-prefixes will be denoted as ( ) = { ∣ ≠ , ∃ ∈ (Σ ∪ {
c|, $})∗ ∶ ∈ { c|} ⋅ Σ∗ ⋅ {$}}.
of width . Let = ( , ) be a PS-free pumping CF( c|, $)Similarly, the set of all basic PS-sufixes will be denoted as
BPref ( , ) = {{ c|} ⋅ ∣ ∈ Σ
∗, and | | < } .
BSuf ( , ) = { ⋅ {$} ∣ ∈ Σ ∗, and | | < }.
In what follows, for a set , ( )
denotes the set of all its subsets.
Definition 6 (Prefix characteristic function) . Let = ( , ) be a PS-free pumping CF( c|, $)-grammar of width > 0 .
A characteristic function of a PS-prefix is the function ℎ() ∶ (
) × BSuf ( , ) → ( BPref ( , )) that for each PS-prefix and a basic sufix assigns the set of all basic PS-prefixes to which the prefix can be reduced, when we reduce the word . Formally: ) = { ∈ BPref ( , ) ∣ ∗ ) is always a nonempty set, as either ∗ • || > and, according to Observation (a2) above, there exists a basic PS-prefix such that 3.1. Equivalence of PS-prefixes and regularity of languages generated by PS-free pumping grammars = has all these properties. classes of ≅ is finite. a PS-free pumping grammar are regular.
Based on the characteristic functions of PS-prefixes, we will define an equivalence on PS-prefixes.
Let = ( , ) be a PS-free CF( c|,$)-grammar of width > 0 . We say that two PS-prefixes and are equivalent, we write ≅ , if for all ∈ BSuf ( , ) it holds ℎ()(, ) = ℎ()(, ).
Lemma 2. Let = ( , ) be a PS-free CF( c|,$)-grammar of width > 0 . The relation ≅ on the set of PS-prefixes by is an equivalence relation of finite index.
Proof: It is easy to see that the relation ≅ is reflexive, symmetric, and transitive, as the equality relation The number of diferent characteristic functions is finite. Therefore, the number of equivalence The following lemma is the key property for showing that the acceptance and rejection languages of
Lemma 3. Let = ( , ) be a PS-free CF( c|,$)-grammar of width > 0 , and let ≅ for some PS-prefixes , by . Then, for each PS-sufix , ∈ ( ) ⇔ ∈ ( ).
Proof: Let and be two PS-prefixes by such that ≅ , and let be a PS-sufix by . Let us suppose ). This means that and a basic PS-sufix ∈ BSuf ( , ) .
∗ PS-free pumping grammar (Definition 4), we get all words , , , and are in (
). ∗ , for some basic PS-prefix ∈ BPref ( , ) ∗ . Using condition (D) from the definition of . The final step follows from the fact that is error- and correctness-preserving, The corresponding statement holds for ( ), which completes the proof that ∈ ( ) ⇔ ∈ only if for all words , ∈ ⇔ ∈ and only if has a finite index.
Let denote the equivalence with respect to a language defined in the following way: if and . According to Theorem 3.1 from [5], the language is regular if Lemma 4. Let = ( , ) be a PS-free pumping CF( c|,$)-grammar of width > 0 and let denote the equivalence with respect to a language = ( each word , it holds that ∈ ⇔ ∈ Proof: Let us consider the relation where = ( prefixes of words from { c|} ⋅ Σ∗ ⋅ {$} are -equivalent.
) defined in the following way: if and only if for . The relation has a finite index.
). As ( ) ⊆ { c|} ⋅ Σ∗ ⋅ {$}, all words that are not exist two words , ∈ ̂ such that ∈
̂ and ∉ ̂. However, all words from = ( If ̂ is an arbitrary language, all words in ̂ do not need to be equivalent to ̂. For example, there can ) ⊆ { c|} ⋅ Σ∗ ⋅ {$} end with a single symbol $. All words in = (
) are equivalent and there are no words outside that can be equivalent to a word in , because the only word that we can append to a word from ( ) to obtain a word from ( ) is the empty word .
Further, we will show that all proper prefixes of words from { c|} ⋅ Σ∗ ⋅ {$} belong to a finite number of diferent equivalence classes with respect to .
For a contradiction, assume that the number of equivalence classes with respect to is infinite. Then, for each ≥ 1 , there exist words 1, 2, … , that are pairwise not equivalent.
If two words are proper prefixes of words from { c|} ⋅ Σ∗ ⋅ {$}, then these words are PS-prefixes. If is greater than the number of equivalence classes with respect to ≅, then there exist two words , , ≠ , such that ≅ . However, according to Lemma 3, the words and are equivalent – a contradiction to the assumption that has an infinite index.
Corollary 2. Let = ( , ) be a PS-free CF( c|,$)-grammar of width > 0 . Then the languages ( ) and ( ) are regular.
Proof: Lemma 4 implies that the relation for = ( ) has a finite index, and according to Theorem 3.1 from [5], the language ( ) is regular. As ( ) = { c|} ⋅ Σ∗ ⋅ {$} (− ), the regularity of the language ( ) follows from the closure properties of regular languages.
Corollary 3. Let = ( , ) be a complete CF( c|, $)-grammar, and ( ) be a non-regular language. Then is not a PS-free pumping CF( c|, $)-grammar.
Lemma 5. For each regular language ⊆ Σ∗, where Σ does not contain sentinels c|, $ there is a CF( c|,$)grammar , = ( , , , ) such that { c|} ⋅ ⋅ {$} = ( , ), and , is a complete PS-free pumping CF( c|,$)-grammar.
Proof: A context-free grammar is a right-linear grammar if each of its rules has at most one nonterminal symbol; the nonterminal appears on the right end of the rule. It is well known that for each regular language there is a right-linear (that is, regular) grammar in the Chomsky normal form such that () = . Additionally, each rule of grammar will have at most two symbols on the right-hand side. During each derivation according to , the sentential form contains at most one nonterminal, and a nonterminal must be repeated in any sequence of derivation steps longer than the number of nonterminals of .
Let be a regular language. Then, its complement ̄ is also a regular language. Let and be right-linear grammars in Chomsky normal form such that ( ) = and ( ) = ̄ .
It is easy to transform both the grammars and into the right-linear grammars , and , such that ( , ) = { c|} ⋅ ( ) ⋅ {$} and ( , ) = { c|} ⋅ ( ) ⋅ {$}, respectively.
Let be the number of nonterminals of , . It is easy to see that , = ( , , , ) is a complete PS-free pumping CF( c|,$)-grammar of width + 1 .
The next theorem says that the internal languages of acceptance languages of complete PS-free pumping CF( c|, $)-grammars characterize the class of regular languages.
Theorem 1. A language is a regular language if and only if there exists a complete PS-free pumping CF( c|,$)-grammar = ( , ), such that = ( ).
Proof: The theorem is a consequence of Corollary 2 and Lemma 5. 4. Comparing PS-free and one-side pumping CF(¢,$)-grammars This section relates PS-free pumping grammars with one-side pumping complete CF(¢,$)-grammars studied in [3] (for their definition see below). Using sample complete CF(¢,$)-grammars, we show that the notions of one-side or PS-free pumping represent diferent restrictions of complete CF( c|,$)-grammars that both restrict them to generate only regular languages.
Let ( , 1, , ,
2, ) be a pumping infix by a CF( c|,$)-grammar . The pumping infix is a core pumping
infix if there is a derivation tree by that corresponds to the derivation
⇒ ∗ c| $ ⇒
∗ c| 1
2 $ ⇒ ∗ c| 1
2 $
(
One-side/Two-side pumping CF( c|,$)-grammars. Let be a CF( c|,$)-grammar. We say that is a left-side pumping CF( c|,$)-grammar if all its core pumping infixes are left-side pumping infixes (Definition
2). Similarly, we say that is a right-side 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 either left-side or right-side pumping CF( c|,$)-grammar. Finally, we say that is a two-side pumping CF( c|,$)-grammar if any of its core pumping infixes is a two-side pumping infix.
The paper [3] showed that one-side pumping complete CF(¢,$)-grammars characterize the class of
Proposition 4 ([3]). Let = ( , ) be a complete one-side pumping CF(¢,$)-grammar. Then, both ( ) and in( ) are regular languages.
On the other hand, the next example shows that a PS-free pumping CF(¢,$)-grammar need not be
one-side pumping.
set of rules:
Example 1. Let
(
be a complete CF( c|,$)-grammar with the following → → → → ∣ , However, the word can also be derived using rules of corresponding pumping infixes are one-side pumping infixes. pumping grammar.
Hence,
(
,
The grammar
(
As ( c|, , , , , $)
is a two-side core pumping infix by
(
is in ( (
(
Actually, we could omit all the rules that include from the grammar, and we would obtain a PS-free pumping grammar that generates the same language as the original grammar and is left-side pumping.
The next corollary is a consequence of Example 1.
Corollary 4. There is a PS-free pumping complete CF( c|, $)-grammar whose acceptance language is regular and which is not a one-side pumping CF( c|,$)-grammar.
The next sample complete CF( c|,$)-grammar generates a regular language, but it is not PS-free pumping grammar. language { c| $ ∣ + > 0}
.
Example 2. Let us consider a complete CF( c|,$)-grammar
(
(
The next corollary follows from the previous example.
Corollary 5. There is a complete CF( c|, $)-grammar
CF( c|,$) grammar such that both (
(
(
The previous example motivates further work. We should study more deeply the conditions for the separation of regular and non-regular complete CF( c|,$)-grammars.
In this paper, we were looking for possibly maximally relaxed constraints based on pumping reductions for a complete CF( c|, $)-grammar, which ensure that the grammar generates regular acceptance and rejection languages. Our approach can be seen as extending the pumping lemma for regular languages.
We have succeeded in the sense that PS-free pumping CF( c|,$)-grammars generate regular languages only. However, the conditions for PS-free pumping grammars are suficient but not necessary to limit the generated languages to the class of regular languages. The obvious open problem is finding conditions necessary and suficient to limit the power of complete CF( c|,$)-grammar to regular languages.
The way to achieve that could start with comparing constraints for non-regularity (from [6]) and for regularity (from this paper) of complete CF( c|, $)-grammars in a uniform way.
Until now, we have not studied the computability and decidability questions connected with complete CF( c|, $)-grammars. New insight could be obtained by comparing the diferences between the grammar complexity of complete CF( c|, $)-grammars and the complexity of their languages.
Marta Vomlelová thanks for support by the institutional support RVO:m 67985807, and by GAČR project 25-18003S. František Mráz and Martin Plátek thank for support by the institutional support RVO:m 67985807.
The authors have not employed any generative AI tools.