Keywords: Idefix-free languages, external contextual grammars, subregular selection languages, computational capacity.

1 Introduction↩︎

Contextual grammars were introduced by Solomon Marcus in [@Marcus.1969] as a formal model for the generation of natural languages. The derivation steps consist in adding contexts to given well-formed sentences, starting from an initial finite basis. Formally, a context is given by a pair \((u, v)\) of words. The external adding to a word \(x\) gives the word \(uxv\); the internal adding to a word \(x\) yields all words \(x_1 u x_2 v x_3\) where \(x_1x_2x_3 = x\). In order to control the derivation process, contextual grammars with selection in a certain family of languages were defined. In such contextual grammars, a context \((u, v)\) may be added only around a word \(x\) if this word belongs to a language which is associated with the context.

The study of external contextual grammars with selection in special regular sets was started by Jürgen Dassow in [@Dassow.2005] and continued by Jürgen Dassow, Florin Manea, and Bianca Truthe (see [@Dassow_Manea_Truthe.2012]), where further subregular families of selection languages were considered. The internal derivation mode with subregular selection languages was investigated in [@DasManTru12b].

In the present paper, we continue this line of research from [@Koedding.Truthe.NCMA24.JALC.2025] and [@Koedding.Truthe.2025.idefix]. We extend the hierarchy of subregular language families by families of infix-free, prefix-free, and suffix-free languages (referred to collectively as idefix-free languages).

The paper is organized as follows. In Section 2, we recall some basic notions and define the subregular language families as well as contextual grammars. In Section 3, we investigate the relations between the families of idefix-free languages and other known subregular language families. In Section 4, we consider external contextual grammars with idefix-free selection languages and compare their generative capacity to that of grammars with other subregular selection languages.

2 Preliminaries↩︎

Throughout the paper, we assume that the reader is familiar with the basic concepts of the theory of automata and formal languages. For details, we refer to [@Rozenberg_Salomaa.1997]. Here we only recall some notations, definitions, and previous results which we need for the present research.

An alphabet is a non-empty finite set of symbols. For an alphabet \(V\), we denote by \(V^*\) and \(V^+\) the set of all words and the set of all non-empty words over \(V\), respectively. The empty word is denoted by \(\lambda\). For a word \(w\) and a letter \(a\), we denote the length of \(w\) by \(|w|\) and the number of occurrences of the letter \(a\) in the word \(w\) by \(|w|_a\). For a set \(A\), we denote its cardinality by \(|A|\).

The reversal of a word \(w\) is denoted by \(w^R\): if \(w=x_1x_2\ldots x_n\) for letters \(x_1,\ldots,x_n\), then \(w^R=x_nx_{n-1}\ldots x_1\). By \(L^R\), we denote the language of all reversals of the words in \(L\): \(L^R=\{\; w^R \mid w\in L\;\}\).

A deterministic finite automaton is a quintuple \[{\cal A}=(V,Z,z_0,F,\delta)\] where \(V\) is a finite set of input symbols, \(Z\) is a finite set of states, \(z_0\in Z\) is the initial state, \(F\subseteq Z\) is a set of accepting states, and \(\delta\) is a transition function \(\delta: Z\times V\to Z\). The language accepted by such an automaton is the set of all input words over the alphabet \(V\) which lead letterwise by the transition function from the initial state to an accepting state.

All the languages accepted by a finite automaton are called regular and form a family denoted by \(\mathit{REG}\). Any subfamily of this set is called a subregular language family.

For a language \(L\) over an alphabet \(V\), we set \[\mathit{Comm}(L) = \{\; a_{i_1}\dots a_{i_n} \mid a_1\dots a_n\in L, \;n\geq 1,\;\{i_1,i_2,\dots ,i_n\}= \{1,2,\dots ,n \}\;\}\] as the commutative closure (the set of all permutations of words) of the language \(L\) and \[\mathit{Circ}(L) = \{\; vu \mid uv\in L,\;u,v\in V^* \;\}\] as the circular closure (the set of all circular shifts of words) of the language \(L\).

For a language \(L\) over an alphabet \(V\), we set \[\begin{align} \mathit{Inf}(L) &=\{\; y \mid xyz\in L \text{ for some } x,z\in V^*\;\},\\ \mathit{Pre}(L) &=\{\; x \mid xy\in L \text{ for some } y\in V^*\;\},\\ \mathit{Suf}(L) &=\{\; y \mid xy\in L \text{ for some } x\in V^*\;\} \end{align}\] as the infix-, prefix-, and suffix-closure of \(L\), respectively. If the language \(L\) is regular, then also \(\mathit{Inf}(L)\), \(\mathit{Pre}(L)\), and \(\mathit{Suf}(L)\) are regular.

2.1 Some Subregular Language Families↩︎

We consider the following restrictions for regular languages. In the following list of properties, we give already the abbreviation which denotes the family of all languages with the respective property. Let \(L\) be a regular language over an alphabet \(V\). With respect to the alphabet \(V\), the language \(L\) is said to be

We remark that monoidal, nilpotent, combinational, (symmetric) definite, ordered, star-free, union-free, star, and (left-, right-, or two-sided) comet languages are regular, whereas non-regular languages of the other types mentioned above exist. Here, we consider among the infix-closed, prefix-closed, suffix-closed, infix-free, prefix-free, suffix-free, commutative, circular, non-counting, and power-separating languages only those which are also regular. By \(\mathit{FIN}\), we denote the family of languages with finitely many words. In [@McNaughton_Papert.1971], it was shown that the families of the regular non-counting languages and the star-free languages are equivalent (\(\mathit{NC}=\mathit{SF}\)).

Some properties of the languages of the classes mentioned above can be found in [@Shyr.1991] (monoids), [@Gecseg_Peak.1972] (nilpotent languages), [@Havel.1969] (combinational and commutative languages), [@Perles_Rabin_Shamir.1963] (definite languages), [@Paz_Peleg.1965] (symmetric definite languages), [@Brzozowski_Jiraskova_Zou.2014] (prefix-closed languages), [@Gill_Kou.1974] and [@Brzozowski_Jiraskova_Zou.2014] (suffix-closed languages), [@Shyr_Thierrin.1974.ord] (ordered languages), [@Kudlek.2004] (circular languages), [@McNaughton_Papert.1971] (non-counting and star free languages), [@Shyr_Thierrin.1974.ps] (power-separating languages), [@Brzozowski.1962] (union-free languages), [@Brzozowski.1967] (star languages), [@Brzozowski_Cohen.1969] (comet languages).

2.2 Contextual Grammars↩︎

Let \({\cal F}\) be a family of languages. A contextual grammar with selection in \({\cal F}\) is a triple \(G=(V,{\cal S},A)\) where

We write a selection pair \((S,C)\) also as \(S\to C\). In the case that \(C\) is a singleton set \(C=\{(u,v)\}\), we also write \(S\to(u,v)\). For a contextual grammar \(G=(V,\{S_1\to C_1, S_2\to C_2,\dots, S_n\to C_n\},A)\), we set \[\ell_{\mathrm{A}}(G) = \max \left\{\: |w| \;|\; w\in A \:\right\},\; \ell_{\mathrm{C}}(G) = \max \left\{\: |uv| \;|\; (u,v)\in C_i, 1\leq i\leq n\:\right\},\; \ell(G) = \ell_{\mathrm{A}}(G)+\ell_{\mathrm{C}}(G)+1.\] We now define the derivation modes for contextual grammars with selection.

Let \(G=(V,{\cal S},A)\) be a contextual grammar with selection. A direct external derivation step in \(G\) is defined as follows: a word \(x\) derives a word \(y\) (written as \(x\Longrightarrow_\mathrm{ex} y\)) if and only if there is a pair \((S,C)\in{\cal S}\) such that \(x\in S\) and \(y=uxv\) for some pair \((u,v)\in C\). Intuitively, one can only wrap a context \((u,v)\in C\) around a word \(x\) if \(x\) belongs to the corresponding selection language \(S\).

A direct internal derivation step in \(G\) is defined as follows: a word \(x\) derives a word \(y\) (written as \(x\Longrightarrow_\mathrm{in} y\)) if and only if there are words \(x_1\), \(x_2\), \(x_3\) with \(x_1x_2x_3=x\) and there is a selection pair \((S,C)\in{\cal S}\) such that \(x_2\in S\) and \(y=x_1ux_2vx_3\) for some pair \((u,v)\in C\). Intuitively, we can only wrap a context \((u,v)\in C\) around a subword \(x_2\) of \(x\) if \(x_2\) belongs to the corresponding selection language \(S\).

By \(\Longrightarrow^*_\mu\) we denote the reflexive and transitive closure of the relation \(\Longrightarrow_\mu\) for \(\mu\in\{\mathrm{ex},\mathrm{in}\}\). The language generated by \(G\) is defined as \(L_\mu(G)=\{\; z \mid x\Longrightarrow^*_\mu z for some x\in A \;\}.\) We omit the index \(\mu\) if the derivation mode is clear from the context.

By \({\cal EC}({\cal F})\), we denote the family of all languages generated externally by contextual grammars with selection in \({\cal F}\). When a contextual grammar works in the external mode, we call it an external contextual grammar.

3 Results on families of idefix-free languages↩︎

In this section, we investigate inclusion relations between various subregular language classes. Figure 1 shows the results.

An arrow from a node \(X\) to a node \(Y\) stands for the proper inclusion \(X \subset Y\). If two families are not connected by a directed path, then they are incomparable. An edge label refers to the paper where the proper inclusion has been shown (in some cases, it might be that it is not the first paper where the respective inclusion has been mentioned, since it is so obvious that it was not emphasized in a publication) or the lemma of this paper where the proper inclusion will be shown.

In the literature, it is often said that two languages are equivalent if they are equal or differ at most in the empty word. Similarly, two families can be regarded to be equivalent if they differ only in the languages \(\emptyset\) or \(\{\lambda\}\). Therefore, the set \(\mathit{STAR}\) of all star languages is sometimes regarded as a proper subset of the set \(\mathit{COM}\) of all (left-, right-, or two-sided) comet languages although \(\{\lambda\}\) belongs to the family \(\mathit{STAR}\) but not to \(\mathit{LCOM}\), \(\mathit{RCOM}\) or \(\mathit{2COM}\). We regard \(\mathit{STAR}\) and \(\mathit{STAR}\setminus\{\{\lambda\}\}\) as different.

We now present some languages which will serve later as witness languages for proper inclusions or incomparabilities.

The language \(L\) contains exactly two words and is therefore finite, yielding \(L \in \mathit{FIN}\). The word \(b\) is not a proper prefix of \(ab\), and \(ab\) is not a prefix of \(b\). Since no word in \(L\) is a proper prefix of another word in \(L\), it follows that \(L \in \mathit{PFR}\). However, since \(b \in L\) is a proper suffix of \(ab \in L\), the language \(L\) is not suffix-free. Therefore, \(L \notin \mathit{SFR}\), and the assertion holds. \(\Box\)

The language \(L\) is finite since it contains exactly two words, hence \(L \in \mathit{FIN}\). The word \(a\) is not a proper suffix of \(ab\), and \(ab\) is not a suffix of \(a\). Since no word in \(L\) is a proper suffix of another word in \(L\), it holds \(L \in \mathit{SFR}\). Furthermore, since \(a \in L\) is a proper prefix of \(ab \in L\), the language \(L\) is not prefix-free. Hence, \(L \notin \mathit{PFR}\), which yields the assertion. \(\Box\)

With the alphabet \(V = \{a\}\), the language \(L\) can be expressed as \(V^*\). Therefore, \(L \in \mathit{MON}\). The word \(a \in L\) is both a proper prefix and a proper suffix of the word \(aa \in L\). Thus, the language \(L\) is neither prefix-free nor suffix-free, which implies \(L \notin \mathit{PFR}\cup \mathit{SFR}\). \(\Box\)

Since the words \(ab\) and \(ba\) have the same length and are not equal, neither can be a proper infix of the other. Thus, \(L \in \mathit{IFR}\). According to [@Nagy.2019], a union-free language is either infinite or contains at most one word. Since \(L\) contains exactly two words, it is not union-free. Therefore, \(L \notin \mathit{UF}\), which yields the assertion. \(\Box\)

The language \(L\) consists of exactly one word and is therefore infix-free, yielding \(L \in \mathit{IFR}\). According to [@Koedding.Truthe.2024], every two-sided comet language is either empty or infinite. Since \(L\) contains exactly one word, \(L \notin \mathit{2COM}\). Furthermore, \(L\) is neither prefix-closed, suffix-closed nor circular because the word \(ab\) is in \(L\), but its proper prefix and proper suffix \(\lambda\) and its circular permutation \(ba\) is not. Consequently, \(L \notin \mathit{PCL}\cup \mathit{SCL}\cup \mathit{CIRC}\). \(\Box\)

Every word in \(L\) contains exactly two occurrences of the letter \(a\), located at the very first and last positions. Because of this, no word in \(L\) can be a proper infix of another word in \(L\). Thus, \(L \in \mathit{IFR}\).

Assuming that \(L\) is non-counting, it follows from the definition that for all words \(x, y, z \in \{a,b\}^*\) and for a number \(k \ge 1\) the equivalence \(x y^k z \in L \iff x y^{k+1} z \in L\) applies. We now set \(x = z = a\) and \(y = b\). If \(k\) is even, \(a b^k a \in L\) but \(a b^{k+1} a \notin L\), which is a contradiction. If \(k\) is odd, \(a b^{k+1} a \in L\) but \(a b^k a \notin L\), which is also a contradiction. It follows that \(L \notin \mathit{NC}\). \(\Box\)

By setting \(X = \{a\} \subseteq V\), the language can be written as \(L = V^*X\). Therefore, \(L \in \mathit{COMB}\). The word \(a \in L\) is a proper prefix and a proper suffix of the word \(aa \in L\), which implies that \(L\) is neither prefix-free nor suffix-free. Consequently, \(L \notin \mathit{PFR}\cup \mathit{SFR}\), and the assertion holds. \(\Box\)

We now prove some inclusion relations.

The inclusions \(\mathit{IFR}\subseteq \mathit{PFR}\) and \(\mathit{IFR}\subseteq \mathit{SFR}\) hold because every prefix and every suffix of a word is also an infix of that word. Thus, any infix-free language is necessarily prefix-free and suffix-free.

The language \(L_1 = \{b,ab\}\) from Lemma 1 is a witness language for the properness of the first inclusion. Since \(L_1 \in \mathit{PFR}\setminus \mathit{SFR}\) and \(\mathit{IFR}\subseteq \mathit{SFR}\), it follows that \(L_1 \in \mathit{PFR}\setminus \mathit{IFR}\).

Similarly, the language \(L_2 = \{a,ab\}\) from Lemma 2 is a witness language for the properness of the second inclusion. Since \(L_2 \in \mathit{SFR}\setminus \mathit{PFR}\) and \(\mathit{IFR}\subseteq \mathit{PFR}\), it follows that \(L_2 \in \mathit{SFR}\setminus \mathit{IFR}\). \(\Box\)

We first show the inclusions \(\mathit{PFR}\subseteq \mathit{PS}\) and \(\mathit{SFR}\subseteq \mathit{PS}\). Let \(L\) be a regular language over an alphabet \(V\) such that \(L \in \mathit{PFR}\) or \(L \in \mathit{SFR}\). Since \(L\) is regular, there exists a deterministic finite automaton accepting \(L\) with \(n\) states. We claim that \(L\) is power-separating with the constant \(m = n\). We show that for any \(x \in V^*\), either \(J_x^n \cap L = \emptyset\) or \(J_x^n \subseteq L\), where \(J_x^n = \{\; x^k \mid k \ge n\;\}\).

If \(x = \lambda\), then \(J_\lambda^n = \{\lambda\}\). If \(\lambda \in L\), then \(J_\lambda^n \subseteq L\); otherwise \(J_\lambda^n \cap L = \emptyset\).

For the case \(x \neq \lambda\), we will show that \(J_x^n \cap L = \emptyset\). Let \(x\in V^*\). Assume for the sake of contradiction that \(J_x^n \cap L \neq \emptyset\). This means there exists an integer \(k \ge n\) such that \(x^k \in L\). Consider the states the DFA ended in after reading the prefixes \(x^0, x^1, \dots, x^n\). Since there are \(n+1\) states the DFA ended in but only \(n\) distinct states, the Pigeonhole Principle dictates that at least two states among them are identical. Let \(0 \leq i < j \leq n\) be two indices with \(\delta(q_0, x^i) = \delta(q_0, x^j)\) and set \(d = j - i\) (note that \(d\geq 1\)). Then \(\delta(q_0, x^t) = \delta(q_0, x^{t+d})\) for all \(t \geq i\). Since \(k \geq n > i\), we obtain \(\delta(q_0, x^{k+d}) = \delta(q_0, x^k) \in F\), so \(x^{k+d} \in L\).

Since \(x^{k+d} = x^k x^d = x^d x^k\) and \(d \ge 1\), the word \(x^k\) is both a proper prefix and a proper suffix of \(x^{k+d}\). Having both \(x^k\) and \(x^{k+d}\) in \(L\) contradicts the assumption that \(L\) is prefix-free or suffix-free. Thus, \(J_x^n \cap L = \emptyset\) holds, which implies \(\mathit{PFR}\subseteq \mathit{PS}\) and \(\mathit{SFR}\subseteq \mathit{PS}\).

The language \(L = \{a\}^*\) from Lemma 3 is a witness for the properness of both inclusions. Since \(\mathit{MON}\subset \mathit{PS}\) and \(L \in \mathit{MON}\), it holds \(L \in \mathit{PS}\). As \(L \notin (\mathit{PFR}\cup \mathit{SFR})\), we obtain \(L \in \mathit{PS}\setminus \mathit{PFR}\) and \(L \in \mathit{PS}\setminus \mathit{SFR}\). \(\Box\)

We now prove the incomparability relations mentioned in Figure 1 which have not been proved earlier. These are the relations regarding the families \(\mathit{PFR}\), \(\mathit{SFR}\), and \(\mathit{IFR}\).

Let \(F \in {\cal F}\) and \(X \in \{\mathit{PFR}, \mathit{SFR}, \mathit{IFR}\}\). Due to the inclusion relations of the subregular families, it suffices to show that there are languages \[\begin{align} L_1 \in \mathit{MON}\setminus (\mathit{PFR}\cup \mathit{SFR}) \text{ and } L_2 \in \mathit{IFR}\setminus \mathit{UF}. \end{align}\]

For the first case, we refer to the language \(L_1 = \{a\}^*\) from Lemma 3. As established there, it holds \(L_1 \in \mathit{MON}\setminus (\mathit{PFR}\cup \mathit{SFR})\). Since \(\mathit{IFR}\subseteq \mathit{PFR}\cap \mathit{SFR}\), it also holds \(L_1 \notin \mathit{IFR}\), which implies \(L_1 \notin X\). Since \(\mathit{MON}\subseteq \mathit{STAR}\subseteq \mathit{UF}\), we have \(\mathit{MON}\subseteq F\) for all \(F \in {\cal F}\). Thus, \(L_1 \in F \setminus X\).

For the second case, we consider the language \(L_2 = \{ab, ba\}\) from Lemma 4. The lemma shows that \(L_2 \in \mathit{IFR}\setminus \mathit{UF}\). Since \(\mathit{IFR}\subseteq \mathit{PFR}\cap \mathit{SFR}\), it holds \(L_2 \in X\). Since \(\mathit{STAR}\subseteq \mathit{UF}\), the relation \(L_2 \notin \mathit{UF}\) implies \(L_2 \notin F\) for all \(F \in {\cal F}\). Thus, \(L_2 \in X \setminus F\).

Since both directions of inclusion are refuted, the assertion holds. \(\Box\)

Let \(F \in {\cal F}\) and \(X \in \{\mathit{PFR}, \mathit{SFR}, \mathit{IFR}\}\). Due to the inclusion relations of the subregular families, it suffices to show that there are languages \[\begin{align} L_1 \in \mathit{COMB}\setminus (\mathit{PFR}\cup \mathit{SFR}) \text{ and } L_2 \in \mathit{IFR}\setminus \mathit{2COM}. \end{align}\]

For the first case, we refer to the language \(L_1 = \{a, b\}^*\{a\}\) from Lemma 7. As established there, \(L_1 \in \mathit{COMB}\setminus (\mathit{PFR}\cup \mathit{SFR})\). Since \(\mathit{IFR}\subseteq \mathit{PFR}\cap \mathit{SFR}\), it also holds \(L_1 \notin \mathit{IFR}\), which implies \(L_1 \notin X\). Since \(\mathit{COMB}\subseteq F\) for all \(F \in {\cal F}\), we have \(L_1 \in F\). Thus, \(L_1 \in F \setminus X\).

For the second case, we consider the language \(L_2 = \{ab\}\) from Lemma 5. The lemma shows that \(L_2 \in \mathit{IFR}\), which implies \(L_2 \in X\), and that \(L_2 \notin \mathit{2COM}\). Since all families \(F \in {\cal F}\) are subsets of \(\mathit{2COM}\), the relation \(L_2 \notin \mathit{2COM}\) implies \(L_2 \notin F\). Thus, \(L_2 \in X \setminus F\).

Since both directions of inclusion are refuted, the assertion holds. \(\Box\)

Let \(F \in {\cal F}\) and \(X \in \{\mathit{PFR}, \mathit{SFR}, \mathit{IFR}\}\). Due to the inclusion relations of the subregular families, it suffices to show that there are languages \[\begin{align} L_1 \in \mathit{FIN}\setminus (\mathit{PFR}\cup \mathit{SFR}) \text{ and } L_2 \in \mathit{IFR}\setminus \mathit{NC}. \end{align}\]

For the first case, we consider the language \(L_1 = \{a, aa\}\). Since \(L_1\) is finite, \(L_1 \in \mathit{FIN}\). The language \(L_1\) is neither prefix-free nor suffix-free, yielding \(L_1 \notin \mathit{PFR}\cup \mathit{SFR}\). Since \(\mathit{IFR}\subseteq \mathit{PFR}\cap \mathit{SFR}\), it also holds \(L_1 \notin \mathit{IFR}\), which implies \(L_1 \notin X\). Due to the inclusions \(\mathit{FIN}\subseteq \mathit{NIL}\subseteq \mathit{DEF}\subseteq \mathit{ORD}\subseteq \mathit{NC}\), we have \(\mathit{FIN}\subseteq F\) for all \(F \in {\cal F}\), and thus \(L_1 \in F\). Therefore, \(L_1 \in F \setminus X\).

For the second case, we refer to the language \(L_2 = \{a(bb)^n a \mid n \ge 0\}\) from Lemma 6. The lemma shows that \(L_2 \in \mathit{IFR}\setminus \mathit{NC}\). Since \(\mathit{IFR}\subseteq \mathit{PFR}\cap \mathit{SFR}\), it holds \(L_2 \in X\). Since all families \(F \in {\cal F}\) are subsets of \(\mathit{NC}\), the relation \(L_2 \notin \mathit{NC}\) implies \(L_2 \notin F\). Thus, \(L_2 \in X \setminus F\).

Since both directions of inclusion are refuted, the assertion holds. \(\Box\)

Let \(F \in {\cal F}\) and \(X \in \{\mathit{PFR}, \mathit{SFR}, \mathit{IFR}\}\). Due to the inclusion relations of the subregular families, it suffices to show that there are languages \[\begin{align} L_1 \in \mathit{ICL}\setminus (\mathit{PFR}\cup \mathit{SFR}) \text{ and } L_2 \in \mathit{IFR}\setminus (\mathit{PCL}\cup \mathit{SCL}). \end{align}\] For the first case, we refer to the language \(L_1 = \{a\}^*\) from Lemma 3. As established there, it holds \(L_1 \in \mathit{MON}\setminus (\mathit{PFR}\cup \mathit{SFR})\). Since \(\mathit{IFR}\subseteq (\mathit{PFR}\cap \mathit{SFR})\), it also holds \(L_1 \notin \mathit{IFR}\), which implies \(L_1 \notin X\). Since \(\mathit{MON}\subseteq \mathit{ICL}\subseteq (\mathit{PCL}\cap \mathit{SCL})\), we have \(\mathit{MON}\subseteq F\) for all \(F \in {\cal F}\), yielding \(L_1 \in F\). Thus, \(L_1 \in F \setminus X\).

For the second case, we consider the language \(L_2 = \{ab\}\) from Lemma 5. The lemma shows that \(L_2 \in \mathit{IFR}\), meaning \(L_2 \in X\), and that \(L_2 \notin \mathit{PCL}\cup \mathit{SCL}\). Since closure under subwords would require the empty word \(\lambda\) to be in the language, which is false for \(L_2\), we also have \(L_2 \notin \mathit{ICL}\). Thus, \(L_2 \notin F\) for all \(F \in {\cal F}\), yielding \(L_2 \in X \setminus F\).

Since both directions of inclusion are refuted, the assertion holds. \(\Box\)

Let \(F \in {\cal F}\) and \(X \in \{\mathit{PFR}, \mathit{SFR}, \mathit{IFR}\}\). Due to the inclusion relations of the subregular families, it suffices to show that there are languages \[\begin{align} L_1 \in \mathit{MON}\setminus (\mathit{PFR}\cup \mathit{SFR}) \text{ and } L_2 \in \mathit{IFR}\setminus \mathit{CIRC}. \end{align}\] For the first case, we refer to the language \(L_1 = \{a\}^*\) from Lemma 3. As established there, it holds \(L_1 \in \mathit{MON}\setminus (\mathit{PFR}\cup \mathit{SFR})\). Since \(\mathit{IFR}\subseteq (\mathit{PFR}\cap \mathit{SFR})\), it also holds \(L_1 \notin \mathit{IFR}\), which implies \(L_1 \notin X\). Since \(\mathit{MON}\subseteq \mathit{COMM}\) and \(\mathit{MON}\subseteq \mathit{CIRC}\), we have \(\mathit{MON}\subseteq F\) for all \(F \in {\cal F}\), yielding \(L_1 \in F\). Thus, \(L_1 \in F \setminus X\).

For the second case, we consider the language \(L_2 = \{ab\}\). No word in \(L_2\) is a proper infix of another, meaning \(L_2 \in \mathit{IFR}\), which implies \(L_2 \in X\). However, \(L_2\) lacks the word \(ba\), violating the closure properties of commutativity and circularity, so \(L_2 \notin (\mathit{COMM}\cup \mathit{CIRC})\). Furthermore, it holds that \(L_2 \notin \mathit{MON}\). Thus, \(L_2 \notin F\) for all \(F \in {\cal F}\), yielding \(L_2 \in X \setminus F\).

Since both directions of inclusion are refuted, the assertion holds. \(\Box\)

From all these relations, the hierarchy presented in Figure 1 follows.

4 Results on subregular control in external contextual grammars↩︎

In this section, we include the families of languages generated by external contextual grammars with selection languages from the subregular families under investigation into the existing hierarchy with respect to external contextual grammars.

If, in a contextual grammar, all selection languages belong to some language family \(X\), then they belong also to every super set \(Y\) of \(X\). Therefore, each language in \(\mathcal{EC}(X)\) is also generated by a contextual grammar with selection languages from \(Y\) and we have the following monotonicity.

Figure 2 shows the inclusion relations between language families which are generated by external contextual grammars where the selection languages belong to subregular classes investigated before. The hierarchy contains results which were already known (marked by a reference to the literature) and results which will be proved in this section (marked by a number which refers to the respective lemma).

We now present some languages which will serve later as witness languages for proper inclusions or incomparabilities.

The external contextual grammar \(G = (\{a,b\}, \{\{a\}^*\{b\} \to (a, \lambda)\}, \{b\})\) generates the language \(L\). For any integers \(m\) and \(n\) with \(m < n\), the word \(a^m b\) is not a prefix of \(a^n b\) since the letter \(b\) appears exactly once at the very end of each word. Thus, the selection language \(\{a\}^*\{b\}\) is prefix-free, yielding \(L_1 \in \mathcal{EC}(\mathit{PFR})\).

Assume \(L \in \mathcal{EC}(\mathit{SFR})\). Any grammar generating the infinite language \(L_1\) from a finite set of axioms must have at least one selection language \(S \in \mathit{SFR}\) containing infinitely many words of \(L\). Thus, there exist integers \(x\) and \(y\) with \(x < y\) such that \(a^x b \in S\) and \(a^y b \in S\). Since \(a^y b = a^{y-x} a^x b\) and \(a^{y-x} \neq \lambda\), the word \(a^x b\) is a proper suffix of \(a^y b\). This contradicts the assumption that \(S \in \mathit{SFR}\). Therefore, \(L_1 \notin \mathcal{EC}(\mathit{SFR})\), which yields the assertion. \(\Box\)

The external contextual grammar \(G = (\{a,b\}, \{\{b\}\{a\}^* \to (\lambda, a)\}, \{b\})\) generates the language \(L\). For any integers \(m\) and \(n\) with \(m < n\), the word \(b a^m\) is not a suffix of \(b a^n\) since the letter \(b\) appears exactly once at the very beginning of each word. Thus, the selection language \(\{b\}\{a\}^*\) is suffix-free, yielding \(L \in \mathcal{EC}(\mathit{SFR})\).

Assume \(L \in \mathcal{EC}(\mathit{PFR})\). A grammar generating the infinite language \(L\) must have a selection language \(S \in \mathit{PFR}\) containing infinitely many words of \(L\). Thus, there exist integers \(x\) and \(y\) with \(x < y\) such that \(b a^x \in S\) and \(b a^y \in S\). Since \(b a^y = b a^x a^{y-x}\) and \(a^{y-x} \neq \lambda\), the word \(b a^x\) is a proper prefix of \(b a^y\). This contradicts the assumption that \(S \in \mathit{PFR}\). Therefore, \(L \notin \mathcal{EC}(\mathit{PFR})\), establishing the assertion. \(\Box\)

The external contextual grammar \(G = (\{a\}, \{\{a\}^* \to (a, \lambda)\}, \{\lambda\})\) generates the language \(L\). Since the only selection language is \(\{a\}^* \in \mathit{MON}\), it holds \(L \in \mathcal{EC}(\mathit{MON})\).

Assuming \(L \in \mathcal{EC}(\mathit{PFR}) \cup \mathcal{EC}(\mathit{SFR})\), the language \(L\) is generated by an external contextual grammar where all selection languages belong entirely to \(\mathit{PFR}\) or entirely to \(\mathit{SFR}\). Since \(L\) is infinite and the grammar has only finitely many selection pairs, at least one selection language \(S\) must contain infinitely many words from \(L\). Thus, there exist integers \(n\) and \(m\) with \(n < m\) such that \(a^n, a^m \in S\). Since \(a^n\) is both a proper prefix and a proper suffix of \(a^m\), the selection language \(S\) is neither prefix-free nor suffix-free. This is a contradiction. Consequently, \(L \notin \mathcal{EC}(\mathit{PFR}) \cup \mathcal{EC}(\mathit{SFR})\), which yields the assertion. \(\Box\)

The external contextual grammar \(G = (\{a,b,c\}, \{\{a\}^* \{c b\} \to (a, \lambda)\}, \{a, b, acb\})\) generates the language \(L_{\textit{pre}}\). For any \(n \neq m\), the word \(a^n c b\) is not a prefix of \(a^m c b\). Thus, the only selection language \(\{a\}^* \{cb\}\) is prefix-free, yielding \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{PFR})\).

Assume \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{PCL}) \cup \mathcal{EC}(\mathit{SCL})\). Any grammar generating the infinite language \(L_{\textit{pre}}\) from a finite set of axioms must have a selection language \(S\) containing infinitely many words of the form \(a^n c b\). The corresponding context must be of the form \((a^p, \lambda)\) with \(p \ge 1\) to generate longer words in \(L_{\textit{pre}}\). If \(S \in \mathit{PCL}\), the proper prefix \(a\) of \(a^n c b\) belongs to \(S\). Since \(a \in L_{\textit{pre}}\), the grammar applies the context \((a^p, \lambda)\) to \(a\), generating the word \(a^{p+1} \notin L_{\textit{pre}}\), a contradiction. If \(S \in \mathit{SCL}\), the proper suffix \(b\) belongs to \(S\). Applying the context \((a^p, \lambda)\) to the word \(b \in L_{\textit{pre}}\) generates \(a^p b \notin L_{\textit{pre}}\), which is also a contradiction. Since \(\mathit{ICL}\subseteq \mathit{PCL}\cap \mathit{SCL}\), we obtain \(L_{\textit{pre}} \notin \mathcal{EC}(\mathit{PCL}) \cup \mathcal{EC}(\mathit{SCL}) \cup \mathcal{EC}(\mathit{ICL})\).

By symmetry, the reversed language \(L_{\textit{suf}} = L_{\textit{pre}}^R\) is generated by an external contextual grammar with the suffix-free selection language \(\{b c\}\{a\}^*\) and the context \((\lambda, a)\), yielding \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR})\). Assuming \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{PCL}) \cup \mathcal{EC}(\mathit{SCL})\) leads to analogous contradictions: a prefix-closed selection language would contain \(b\), triggering the generation of the word \(b a^p \notin L_{\textit{suf}}\), while a suffix-closed selection language would contain \(a\), triggering \(a^{p+1} \notin L_{\textit{suf}}\). Thus, \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR}) \setminus (\mathcal{EC}(\mathit{PCL}) \cup \mathcal{EC}(\mathit{SCL}) \cup \mathcal{EC}(\mathit{ICL}))\). \(\Box\)

First, we show that \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{PFR}) \setminus \mathcal{EC}(\mathit{NC})\).

The contextual grammar \(G = (\{a,b,c,d\}, \{S_1 \to C_1, S_2 \to C_2\}, \{ccd\})\) with

\[\begin{align} S_1 &= \{c\}^*\{d\}, & S_2 &= \{ a^p b c^{2n} d b \mid n \geq 1, p \geq 0 \},\\ C_1 &= \{(c, \lambda), (b, b)\}, & C_2 &= \{(a, \lambda)\} \end{align}\]

generates the language \(L_{\textit{pre}}\) and all selection languages are prefix-free. The selection language \(S_1\) is prefix-free since every word ends with its only letter \(d\). Similarly, \(S_2\) is prefix-free because all its words end with a \(b\) that follows the only \(d\) in the word, meaning no word in \(S_2\) can be a proper prefix of another word in \(S_2\).

It can be seen as follows that the language \(L_{\textit{pre}}\) is generated. The axiom \(ccd\) is in the first selection language \(S_1\). If we apply the first rule \((c, \lambda)\) of \(C_1\) arbitrarily often, we get the words of the form \(c^n d\) for \(n \geq 2\). If we apply the second context \((b, b)\) of the first selection component to these words, we get the words \(b c^n d b\) for \(n \geq 2\). As soon as we use this context, our word begins with \(b\) and is no longer in the first selection language.

If the number of letters \(c\) in our word is even, meaning the word is of the form \(b c^{2n} d b\), it belongs to the second selection language \(S_2\). We can then repeatedly apply the rule of the second selection component \((a, \lambda)\) to derive any word of the form \(a^m b c^{2n} d b\) for \(m \geq 1\). No other words are created in the process. Words with an odd number of \(c\)’s do not trigger the context in \(S_2\). Thus, we see that the grammar generates the language \(L_{\textit{pre}}\).

We assume that \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{NC})\) holds. Then, there is a contextual grammar \(G' = (\{a,b,c,d\}, \mathcal{S}', B')\) where all selection languages are non-counting and \(L_{\textit{pre}} = L(G')\).

Since every selection language \(S\) is non-counting, there is a natural number \(k\) for each language such that, for all words \(x, y, z \in V^*\), it holds \(x y^k z \in S \iff x y^{k+1} z \in S\). We denote our selection languages by \(S^{(k)}\) where \(k\) is the smallest natural number in the sense of the definition of non-counting languages.

Furthermore, we define \(p = \max\{ k \mid (S^{(k)}, C) \in \mathcal{S}' \}\). Thus, the following statement applies to every selection language \(S^{(k)}\): For all words \(x, y, z \in V^*\), it holds \[x y^p z = x y^k y^{p-k} z \in S^{(k)} \iff x y^{k+1} y^{p-k} z = x y^{p+1} z \in S^{(k)}. \label{eq:nc95prop}\tag{1}\]

Since the language \(L_1\) contains words with an arbitrary even number of letters \(c\), there is a derivation \[w_0 \stackrel{*}{\implies} w_1 \implies u w_1 v\] with \(w_0 \in B'\), \(u w_1 v \in L_1\), \(|w_1|_c > p + \ell(G')\), \(|w_1|_a = 0\) and \(|uv|_a > 0\). We now distinguish two cases. In the first case, the word \(w_1\) begins with letter \(b\); in the second case, the word \(w_1\) begins with letter \(c\).

Case 1 (\(w_1\) starts with \(b\)): In this case, we have \(w_1 = b c^k d b\) with \(k > p + \ell(G')\). Since \(u w_1 v\) belongs to the language \(L_1\), \(k\) is even. Let \(S\) be the selection language used in the derivation step \(w_1 \implies u w_1 v\). Since \(w_1 \in S\), we obtain according to the relation (1 ) \[w_1 = b c^p c^{k-p} d b \in S \iff b c^{p+1} c^{k-p} d b = b c^{k+1} d b \in S.\] Since \(b c^{k+1} d b\) is in \(L_3\) and, thus, also in \(L_{\textit{pre}}\), the word \(u b c^{k+1} d b v\) is also derived. However, since \(k + 1\) is odd and \(|uv|_a > 0\), this word is not in \(L_{\textit{pre}}\), which is a contradiction to \(L_{\textit{pre}} = L(G')\).

Case 2 (\(w_1\) starts with \(c\)): Then, \(w_1 = c^k d\) follows with \(k > p + \ell(G')\). Since \(u w_1 v \in L_1\) holds, it follows that \(u = a^m b\) for a number \(m \geq 1\) and \(v = b\) (since \(|uv|_a > 0\)). Let \(S\) denote the selection language used in the derivation step \(w_1 \implies u w_1 v\). Since \(w_1 \in S\), we obtain according to the relation (1 ) \[w_1 = c^p c^{k-p} d \in S \iff c^{p+1} c^{k-p} d = c^{k+1} d \in S.\] Since \(c^{k+1} d\) belongs to \(L_2\) and, thus, to \(L_{\textit{pre}}\), the word \(u c^{k+1} d v\) is also derived. Since \(|uv|_a > 0\) and the word \(u c^k d v\) belongs to \(L_1\), the number \(k\) is even and \(k+1\) is an odd number. Consequently, the derived word \(a^m b c^{k+1} d b\) does not belong to the language \(L_1\) and also not to \(L_{\textit{pre}}\), which is a contradiction to \(L_{\textit{pre}} = L(G')\).

Since all cases lead to a contradiction, the assumption that \(L_{\textit{pre}}\) is in \(\mathcal{EC}(\mathit{NC})\) is false.

By symmetry, an analogous argument holds for the reversed language \(L_{\textit{suf}} = L_{\textit{pre}}^R\). A contextual grammar with symmetrically defined suffix-free selection languages generates \(L_{\textit{suf}}\). Assuming \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{NC})\) yields a similar contradiction when pumping the non-counting sequences of letters \(c\). Therefore, we also have \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR}) \setminus \mathcal{EC}(\mathit{NC})\). \(\Box\)

The external contextual grammar \(G = (\{a,b,c\}, \{S_1 \to C_1, S_2\to C_2\}, \{ababc, babca\})\) with

\[\begin{align} S_1 &= \{\; (ab)^{n} c \mid n \ge 2\;\}, & S_2 &= \{\; (ba)^{n} b c a \mid n \ge 1\;\},\\ C_1 &= \{\left(ab, \lambda\right)\}, & C_2 &= \{(ba, \lambda)\} \end{align}\]

generates the language \(L_{\textit{pre}}\). Every word in the first selection language \(\{\; (ab)^{n} c \mid n \ge 2\;\}\) ends with \(c\), whereas any of its proper prefixes ends with \(a\) or \(b\). Thus, it is prefix-free. Similarly, every word in the second selection language \(\{\; (ba)^{n} b c a \mid n \ge 1\;\}\) ends with the subword \(ca\). Since the letter \(c\) occurs exactly once in each word, no proper prefix can end with \(ca\). Therefore, both selection languages are prefix-free, yielding \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{PFR})\).

Assume \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{CIRC})\). Any grammar generating \(L_{\textit{pre}}\) must use a circular selection language \(S \in \mathit{CIRC}\) containing a word \(w_1 = (ab)^n c \in L_{\textit{pre}}\) (with \(n \ge 2\)) and apply a context \(((ab)^m, \lambda)\) to it to derive the longer word \((ab)^{n+m} c\) for a natural number \(m \geq 1\). Since \(S\) is closed under circular shifts, shifting the first letter \(a\) to the end of \(w_1\) yields the word \((ba)^{n-1} b c a\), which also belongs to \(S\). Since this shifted word is a word in \(L_{\textit{pre}}\), the context \(((ab)^m, \lambda)\) can be applied to this word, too. This generates the word \((ab)^m(ba)^{n-1} b c a\), which contains the subword \(bb\). However, all words in \(L_{\textit{pre}}\) consist of alternating letters \(a\) and \(b\) before the letter \(c\). This contradiction implies \(L_{\textit{pre}} \notin \mathcal{EC}(\mathit{CIRC})\).

By symmetry, the reversed language \(L_{\textit{suf}} = L_{\textit{pre}}^R\) is generated by an external contextual grammar with the suffix-free selection languages \(\{\; c(ba)^{n} \mid n \ge 2\;\}\) and \(\{\; acb(ab)^{n} \mid n \ge 1\;\}\), yielding \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR})\). Assuming \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{CIRC})\) forces the application of the context \((\lambda, ba)\) to the circularly shifted
word \(acb(ab)^{n-1} \in L_{\textit{suf}}\), generating a word with the subword \(bb\), which is a contradiction. Thus, \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR}) \setminus \mathcal{EC}(\mathit{CIRC})\). \(\Box\)

The external contextual grammar \(G = (\{a,b,c\}, \{\{\; a^n b c \mid n \ge 1\;\} \to (a, \lambda)\}, \{\lambda, abc\})\) generates the language \(L_{\textit{pre}}\). Every word in the selection language \(\{\; a^n b c \mid n\ge 1\;\}\) ends with \(c\), while any proper prefix ends with \(a\) or \(b\). Thus, the selection language is prefix-free, yielding \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{PFR})\).

Assume \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{STAR})\). Any grammar generating the infinite language \(L_{\textit{pre}}\) must use a star selection language \(S \in \mathit{STAR}\) to extend words of the form \(a^n b c\). To generate longer words in \(L_{\textit{pre}}\), the corresponding context must be \((a^k, \lambda)\) for some \(k \ge 1\). By definition of the Kleene star, every star language contains the empty word, so \(\lambda \in S\). Furthermore, since \(\lambda \in L_{\textit{pre}}\), the context \((a^k, \lambda)\) can be applied to this word, generating the word \(a^k\). Since \(k \ge 1\), it holds \(a^k \neq \lambda\) and \(a^k \notin L_{\textit{pre}}\), which is a contradiction. Therefore, \(L_{\textit{pre}} \notin \mathcal{EC}(\mathit{STAR})\).

By symmetry, the reversed language \(L_{\textit{suf}} = L_{\textit{pre}}^R\) is generated by an external contextual grammar with the suffix-free selection language \(\{\; cba^n \mid n \ge 1\;\}\) and the context \((\lambda, a)\), yielding \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR})\). Assuming \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{STAR})\) leads to a similar contradiction: a selection language \(S \in \mathit{STAR}\) contains \(\lambda\), allowing the application of the corresponding context \((\lambda, a^k)\) to the axiom \(\lambda\). This generates the word \(a^k \notin L_{\textit{suf}}\). Thus, \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR}) \setminus \mathcal{EC}(\mathit{STAR})\). \(\Box\)

First, we show that \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{PFR})\). The external contextual grammar \(G = (\{a,c,d\}, {\cal S}, \{d\})\) with the selection pairs \({\cal S}= \{(S_1, C_1), (S_2, C_2)\}\) defined as

\[\begin{align} S_1 &= \{\; a^n d \mid n \ge 0\;\}, & S_2 &= \{\; a^m d a^n d \mid m\ge 0,\;n\ge 0\;\},\\ C_1 &= \{(a, \lambda), (c, \lambda), (d, \lambda)\}, & C_2 &= \{(a, \lambda)\} \end{align}\]

generates \(L_{\textit{pre}}\). Every word in \(S_1\) ends with exactly one \(d\). Every word in \(S_2\) contains exactly two occurrences of the letter \(d\) and ends with the second one. Thus, no word in \(S_1\) or \(S_2\) can be a proper prefix of another word within the same selection language, yielding \(S_1, S_2 \in \mathit{PFR}\).

Starting from the axiom \(d\), applying \((a, \lambda)\) from \(C_1\) generates the base set \(a^* d\). From any word \(a^n d \in S_1\), applying \((c, \lambda)\) generates \(c a^n d\). Since these words start with \(c\), they neither belong to \(S_1\) nor \(S_2\), halting their derivation. Applying \((d, \lambda)\) from \(C_1\) to \(a^n d\) generates \(d a^n d\), which belongs to \(S_2\). Applying \((a, \lambda)\) from \(C_2\) iteratively to words in \(S_2\) generates \(a^m d a^n d\). Since these words have two letters \(d\), they do not belong to \(S_1\). Thus, \(G\) generates \(L_{\textit{pre}}\), yielding \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{PFR})\).

Assume that \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{SYDEF})\) via some grammar \(G' = (V, {\cal S}', A')\). In order to generate the infinite subset \(\{ c a^n d \mid n \ge 0 \}\), \(G'\) must apply contexts to shorter words from \(L_{\textit{pre}}\). Since external contexts only wrap words, and no word in this subset can be derived from another within it, infinitely many \(c a^n d\) must be derived from \(z = a^m d\) using the context \((c a^{n-m}, \lambda)\) for some \(m < n\).

This requires a selection pair \((S, C) \in {\cal S}'\) with \(a^m d \in S\) and \((c a^{n-m}, \lambda) \in C\). Since \(S \in \mathit{SYDEF}\), it holds \(S = E V_S^* H\) for an alphabet \(V_S\) and regular languages \(E\subseteq V_S^*\) and \(H\subseteq V_S^*\). Since \(a^m d \in S\), the alphabet \(V_S\) contains at least the letters \(a\) and \(d\). The word \(a^m d\) factors as \(e x h\) with \(e \in E\) and \(h \in H\). This restricts the factorization to the following three cases:

Case 1: \(h = \lambda\). Then \(e x = a^m d\). The letter \(d\) is either in \(e\) or in \(x\).

• Subcase 1a (\(d\) is in \(e\)): Then \(e = a^m d\) and \(x = \lambda\). Thus, \(\{a^m d\} V_S^* \subseteq S\). Since \(d \in V_S^*\), the word \(w = a^m d d\) belongs to \(S\). Since \(w \in L_{\textit{pre}}\), it is a word generated by \(G'\). Applying the context gives \(c a^{n-m} a^m d d = c a^n d d \notin L_{\textit{pre}}\), which is a contradiction.

• Subcase 1b (\(d\) is in \(x\)): Then \(e = a^i\) for some \(i \le m\). Thus, \(a^i V_S^* \subseteq S\). Since \(d a d \in V_S^*\), the word \(w = a^i d a d\) belongs to \(S\). Since \(w \in L_{\textit{pre}}\), it is generated by \(G'\). Applying the context gives \(c a^{n-m} a^i d a d \notin L_{\textit{pre}}\), which is a contradiction.

Case 2: \(h = d\). Then \(e x = a^m\), meaning \(e = a^i\) for some \(i \le m\). Thus, \(a^i V_S^* d \subseteq S\). Since \(d a \in V_S^*\), the word \(w = a^i (d a) d = a^i d a d\) belongs to \(S\). Since it belongs to \(L_{\textit{pre}}\), it is generated by \(G'\). Applying the context gives \(c a^{n-m} a^i d a d \notin L_{\textit{pre}}\), which is a contradiction.

Case 3: \(h = a^j d\) for some \(j \ge 1\). Then \(e x = a^{m-j}\), meaning \(e = a^i\) for some \(i \le m-j\). Thus, \(a^i V_S^* a^j d \subseteq S\). Since \(d \in V_S^*\), the word \(w = a^i d a^j d\) belongs to \(S\). Since it belongs to \(L_{\textit{pre}}\), it is generated by \(G'\). Applying the context gives \(c a^{n-m} a^i d a^j d \notin L_{\textit{pre}}\), which is a contradiction.

Since all possible factorizations inevitably cause \(G'\) to apply the context to a word of \(L_{\textit{pre}}\) with two letters \(d\), it generates a word starting with \(c\) but containing two \(d\)’s. Since \(L_{\textit{pre}}\) restricts words starting with \(c\) to have exactly one \(d\), a word is generated which does not belong to \(L_{\textit{pre}}\). Thus, \(L_{\textit{pre}} \notin \mathcal{EC}(\mathit{SYDEF})\). \(\Box\)

Let \(L \in \mathcal{EC}(\mathit{SYDEF})\). By definition, there exists an external contextual grammar \(G = (V, {\cal S}, A)\) such that \(L_{\textit{ex}}(G) = L\), and all selection languages in \({\cal S}\) belong to \(\mathit{SYDEF}\). Let \({\cal S}= \{(S_1, C_1), \dots, (S_k, C_k)\}\).

We construct a new external contextual grammar \(G^R = (V, {\cal S}^R, A^R)\) to generate the reversed language \(L^R\). We define the components of \(G^R\) as follows:

• \(A^R = \{ w^R \mid w \in A \}\) is the set of reversed axioms.

• For each selection pair \((S_i, C_i) \in {\cal S}\), we create a reversed selection pair \((S_i^R, C_i^R) \in {\cal S}^R\), where:

  • \(S_i^R = \{ w^R \mid w \in S_i \}\),

  • \(C_i^R = \{ (v^R, u^R) \mid (u, v) \in C_i \}\).

First, we must verify that all selection languages in \(G^R\) belong to \(\mathit{SYDEF}\). Let \(S \in \mathit{SYDEF}\) be a selection language from \(G\). By definition, \(S\) can be represented as \(S = G_S V_S^* H_S\) for some regular languages \(G_S\) and \(H_S\) over an alphabet \(V_S \subseteq V\). The reversal of \(S\) is given by: \[S^R = (G_S V_S^* H_S)^R = H_S^R (V_S^*)^R G_S^R = H_S^R V_S^* G_S^R.\] Since the family of regular languages is closed under reversal, both \(H_S^R\) and \(G_S^R\) are regular languages. Therefore, \(S^R\) matches the definition of a symmetric definite language, yielding \(S^R \in \mathit{SYDEF}\).

Next, we show the equality \(L_{\textit{ex}}(G^R) = L^R\). We prove this by showing that \(w \in L_{\textit{ex}}(G)\) if and only if \(w^R \in L_{\textit{ex}}(G^R)\). This equivalence holds trivially for the base cases, since \(w \in A \iff w^R \in A^R\). For the derivation steps, suppose \(w_{j+1}\) is derived from \(w_j\) in \(G\). This means there is a selection pair \((S_i, C_i) \in {\cal S}\) such that \(w_j \in S_i\) and \(w_{j+1} = u w_j v\) for some \((u, v) \in C_i\). By our construction of \(G^R\), the reversed word \(w_j^R\) belongs to \(S_i^R\), and the pair \((v^R, u^R)\) belongs to \(C_i^R\). Applying this context to \(w_j^R\) in \(G^R\) yields: \[v^R w_j^R u^R = (u w_j v)^R = w_{j+1}^R.\] Thus, every derivation step \(w_j \implies w_{j+1}\) in \(G\) corresponds exactly to a derivation step \(w_j^R \implies w_{j+1}^R\) in \(G^R\), and vice versa.

Consequently, \(G^R\) generates exactly all reversed words of \(L\). Since \(G^R\) is an external contextual grammar with selection in \(\mathit{SYDEF}\), it follows that \(L^R = L_{\textit{ex}}(G^R) \in \mathcal{EC}(\mathit{SYDEF})\), concluding the proof. \(\Box\)

First, we show that \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR})\). The external contextual grammar \(G = (\{a,c,d\}, {\cal S}, \{d\})\) with the selection pairs \({\cal S}= \{(S_1, C_1), (S_2, C_2)\}\) defined as

\[\begin{align} S_1 &= \{\; d a^n \mid n \ge 0 \;\}, & S_2 &= \{\; d a^m d a^n \mid n\ge 0,\;m \ge 0 \;\},\\ C_1 &= \{(\lambda, a), (\lambda, c), (\lambda, d)\}, & C_2 &= \{(\lambda, a)\} \end{align}\]

generates \(L_{\textit{suf}}\). Every word in \(S_1\) begins with exactly one \(d\). Every word in \(S_2\) contains exactly two occurrences of the letter \(d\) and begins with the first one. Thus, no word in \(S_1\) or \(S_2\) can be a proper suffix of another word within the same language, yielding \(S_1, S_2 \in \mathit{SFR}\). By structural symmetry to Lemma 23, the contexts independently append the respective mirrored characters to the right side, generating the language \(L_{\textit{suf}}\). Thus, \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SFR})\).

Assume that \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SYDEF})\) via some grammar \(G'\). The property of a language belonging to the class \(\mathcal{EC}(\mathit{SYDEF})\) is closed under word reversal because the reverse of any symmetric definite selection language \(S = G V^* H\) is \(S^R = H^R V^* G^R\), which is again symmetric definite ([@Olejar_Szabari.2023]). Since external contextual derivations are completely symmetric, with Lemma 24, it follows that \(L_{\textit{suf}} \in \mathcal{EC}(\mathit{SYDEF})\) implies \(L_{\textit{suf}}^R \in \mathcal{EC}(\mathit{SYDEF})\).

Since \(L_{\textit{suf}}^R = (L_{\textit{pre}}^R)^R = L_{\textit{pre}}\), this would imply that \(L_{\textit{pre}} \in \mathcal{EC}(\mathit{SYDEF})\). However, as established in Lemma 23, \(L_{\textit{pre}} \notin \mathcal{EC}(\mathit{SYDEF})\). From this contradiction, it follows that \(L_{\textit{suf}} \notin \mathcal{EC}(\mathit{SYDEF})\). \(\Box\)

We now prove an equivalence and some inclusion relations.

Every finite language \(L\) over an alphabet \(V\) is generated by the external contextual grammar \(G = (V, \emptyset, L)\). Since the set of selection rules is empty, the condition is satisfied, yielding \(\mathit{FIN}\subseteq \mathcal{EC}(\mathit{IFR})\).

Conversely, let \(G = (V, {\cal S}, A)\) be an external contextual grammar with \(k\) selection pairs where all selection languages belong to \(\mathit{IFR}\). Assume \(L_{ex}(G)\) is infinite. Since the set of axioms \(A\) and all context sets are finite, the grammar must produce arbitrarily long derivation sequences. In any derivation sequence with more than \(k\) steps, the Pigeonhole Principle implies that at least one selection language \(S\) is used in two distinct steps \(i\) and \(j\) (with \(i < j\)). Thus, the used words \(w_i\) and \(w_j\) both belong to \(S\). Since external contextual derivations increase the word length, \(w_i\) is a proper infix of \(w_j\). This contradicts \(S \in \mathit{IFR}\). Therefore, the length of any derivation sequence is bounded by \(k\). Expanding a finite set of axioms at most \(k\) times using finite sets of contexts yields only a finite set of words. Thus, \(L_{ex}(G)\) is finite, yielding \(\mathcal{EC}(\mathit{IFR}) \subseteq \mathit{FIN}\). \(\Box\)

First, we show the inclusions \(\mathcal{EC}(\mathit{PFR}) \subseteq \mathcal{EC}(\mathit{PS})\) and \(\mathcal{EC}(\mathit{SFR}) \subseteq \mathcal{EC}(\mathit{PS})\). Since the inclusions \(\mathit{PFR}\subseteq \mathit{PS}\) and \(\mathit{SFR}\subseteq \mathit{PS}\) hold for the families of selection languages, any external contextual grammar with selection languages in \(\mathit{PFR}\) or \(\mathit{SFR}\) is also an external contextual grammar with selection languages in \(\mathit{PS}\). Thus, every language generated by the former can also be generated by the latter, yielding \(\mathcal{EC}(\mathit{PFR}) \subseteq \mathcal{EC}(\mathit{PS})\) and \(\mathcal{EC}(\mathit{SFR}) \subseteq \mathcal{EC}(\mathit{PS})\).

To show that these inclusions are proper, we consider the language \(L = \{a\}^*\) from Lemma 18. As established in that lemma, \(L \in \mathcal{EC}(\mathit{MON})\). Since \(\mathit{MON}\subseteq \mathit{PS}\), it follows that \(\mathcal{EC}(\mathit{MON}) \subseteq \mathcal{EC}(\mathit{PS})\), which yields \(L \in \mathcal{EC}(\mathit{PS})\). Furthermore, Lemma 18 proves that \(L \notin \mathcal{EC}(\mathit{PFR}) \cup \mathcal{EC}(\mathit{SFR})\).

Consequently, \(L \in \mathcal{EC}(\mathit{PS}) \setminus \mathcal{EC}(\mathit{PFR})\) and \(L \in \mathcal{EC}(\mathit{PS}) \setminus \mathcal{EC}(\mathit{SFR})\), proving that the inclusions are proper. \(\Box\)

By Lemma 26, it holds \(\mathcal{EC}(\mathit{IFR}) = \mathit{FIN}\). Every finite language is generated by an external contextual grammar with an empty set of selection rules, satisfying the requirement for prefix-free or suffix-free selection languages. Thus, \(\mathcal{EC}(\mathit{IFR}) \subseteq \mathcal{EC}(\mathit{PFR})\) and \(\mathcal{EC}(\mathit{IFR}) \subseteq \mathcal{EC}(\mathit{SFR})\) by Lemma 15.

Since \(\mathcal{EC}(\mathit{PFR})\) and \(\mathcal{EC}(\mathit{SFR})\) contain infinite languages (as shown by the witness languages, e.g. in Lemma 19), while \(\mathcal{EC}(\mathit{IFR})\) contains only finite languages, both inclusions are proper. \(\Box\)

By Lemma 26, it holds \(\mathcal{EC}(\mathit{IFR}) = \mathit{FIN}\). Since \(\mathit{FIN}= \mathcal{EC}(\mathit{FIN})\) (as shown in [@Istrail.1978]), the equality \(\mathcal{EC}(\mathit{IFR}) = \mathcal{EC}(\mathit{FIN})\) follows directly. \(\Box\)

With the languages from the previous lemmas, the incomparabilities depicted in Figure 2 can be shown.

5 Conclusion and future work↩︎

In this paper, we have continued the investigation of subregular language families and their application as selection languages in contextual grammars. We have introduced the families of prefix-free, suffix-free, and infix-free languages (idefix-free languages) and established their exact positions within the existing hierarchy of subregular language families. Furthermore, we have comprehensively examined the generative capacity of external contextual grammars regulated by these new families, extending the known inclusion diagrams.

For future work, it remains an ongoing effort to complete the hierarchies of subregular language families and the corresponding families of externally and internally generated contextual languages. As previously noted, the extension of the hierarchy with various other families of definite-like languages (for instance, ultimate definite, central definite, and non-initial definite languages) is currently under investigation. Furthermore, it is planned to unify the extended hierarchy of subregular language families with the hierarchies of language families generated by contextual grammars defined by limited resources (e. g., the number of contexts, the number of selection rules, or the size of the contexts). Finally, applying these specific subregular restrictions to other formal frameworks, such as tree-controlled grammars or networks of evolutionary processors, presents an intriguing direction for upcoming studies. In addition, answering various decidability and complexity questions regarding the families investigated in this work is high on our research agenda.