On the computational completeness of several descriptional complexity restrictions of semi-conditional grammars

Abstract

A semi-conditional grammar, introduced by Gheorghe Păun, is a form of regulated rewriting system where each rule consists of a context-free core rule $A \to w$ along with two strings $w_{+}$ , $w_{-}$ . The rule is applicable if $w_{+}$ (the positive condition) occurs as a substring of the current sentential form, but $w_{-}$ (the negative condition) does not. The maximum lengths i, j of the positive or negative conditional strings, respectively, give a natural measure of descriptional complexity, known as the degree of such grammars. Employing several normal form results on phrase-structure grammars as derived in particular by Viliam Geffert, we improve on previously obtained results by reducing the number of nonterminals of semi-conditional grammars of a given degree $(i, j)$ while maintaining computational completeness of the said mechanisms.

Keywords

Semi-conditional grammars permitting contexts forbidden contexts nonterminals conditional rules descriptional complexity measures

1. Introduction

One of the key areas in modern formal language theory is descriptional complexity. In a nutshell, this area investigates how succinct can a grammatical device, automaton, or rewriting system represent a formal language class (with respect to a certain complexity measure). You can also see this as applying the parsimony principle (or Occam’s razor) to mechanisms that describe formal language classes. This is particularly interesting for devices that are able to describe all recursively enumerable languages, as they are then as powerful as any computational device might ever be according to the famous hypothesis of Church and Turing. For more details on this part of formal language theory (or computability theory) and on applying the parsimony principle, we refer to [6].

In this paper, we focus on the nonterminal complexity of semi-conditional grammars of a certain degree so that they still achieve computational completeness, i.e., they still characterize the class of recursively enumerable languages (denoted by RE). This includes questions like: Does there exist a semi-conditional grammar $G_{L}$ for any RE language L such that $G_{L}$ has degree $(2, 1)$ and uses only six nonterminals? We will answer this question affirmatively in this paper, while it is left as an open question if five nonterminals suffice for this degree.

To arrive at such results, it is often helpful to make use of other similar results and to simulate the corresponding devices. Among the most often used ones are the normal forms for type-0 grammars provided by Geffert in [12], because they also use very few nonterminals to characterize RE.

Descriptional complexity measures as studied in this paper were first introduced by Gruska concerning context-free grammars in [13,14] under the umbrella of classification of context-free languages. Clearly, this study was focussing on subclasses of the context-free languages, and in contrast to what can be observed when describing recursively enumerable languages, especially bounding the number of nonterminals in context-free grammars yields an infinite hierarchy of language classes. To underline the importance and history of nonterminal complexity in the context of regulated rewriting, we refer to [2,7,22].

A semi-conditional grammar (in short, SCG) is an extension of context-free grammar (introduced by Gh. Păun in [21]) in which each rule is associated with two strings called the permitting and forbidden1 strings. A rule can be applied to a sentential form w only if w contains the permitting string (i.e., positive context) and does not contain the forbidden string (i.e., negative context) as a subword. The maximal length of the permitting string (say i) and the forbidden string (say j) constitutes the degree of the grammar and is denoted by $(i, j)$ . A SCG is termed simple if for each rule at most either the permitting string or the forbidden string is present; refer to [19]. If both these control strings are absent in a rule, then the rule is said to be an unconditional. Otherwise the rule is termed conditional. In the field of SCGs, we would like to point to [15–17,20,22], mainly contributed by Meduna, Masopust, Vaszil and Okubo. It is known that even SCGs of degree $(1, 1)$ are computationally complete, i.e., they characterize the language family RE; see [16]. However, the published constructions do not provide a bound on the number of nonterminals for these grammars.2 This is why we have put a * in the corresponding entries of the table, as it is usual in such a situation, and in fact, one could replace the expressions involving $| P_{c f} |$ also by *, but we refrained from doing so, as we consider the present formulation to be more informative.

Table 1
Survey on nonterminal complexity results for semi-conditional grammars.

Degree $(i, j)$ # Nonterminals # Conditional Rules Reference

(1,1) * * [16]

(2,1) 8 7 [17]

(2,1) 7 6 [20]

(2,1) 6 $7 + | P_{c f} |$ Thm. 1

(2,2) 6 6 Thm. 2

(3,1) 5 $9 + 2 (| T | + 1) + | P_{c f} |$ Thm. 3

(3,1) 6 13 Thm. 4

Degree $(i, j)$	# Nonterminals	# Conditional Rules	Reference
(1,1)	*	*	[16]
(2,1)	8	7	[17]
(2,1)	7	6	[20]
(2,1)	6	$7 + \| P_{c f} \|$	Thm. 1
(2,2)	6	6	Thm. 2
(3,1)	5	$9 + 2 (\| T \| + 1) + \| P_{c f} \|$	Thm. 3
(3,1)	6	13	Thm. 4

For SCGs of degree $(2, 1)$ , we improve on the previous result (due to [20]) of seven nonterminals, bringing it down to six. For semi-conditional grammars of degree $(3, 1)$ , also nothing better than the sufficiency of seven nonterminals was known. We reduce this bound to five by a non-trivial use of another normal form result of Geffert. We survey the previously known results and the new results obtained in this paper in Table 1, along with indicating the number of conditional rules. In Table 1, T refers to the terminal alphabet and $P_{c f}$ to a subset of the context-free rules of the given type-0 grammar of a special form; see Remark 2. Notice that if we neglect the number of conditional rules as a descriptional complexity aspect, our results improve on all previously published ones, sometimes trading off degree parameters and number of nonterminals.

Remark 1.

Observe that even when we put the size of $P_{c f}$ into the account of the number of conditional rules, this does not mean that we necessarily have arbitrarily large numbers of them to get, for instance, non-recursive (undecidable) languages. To the contrary, recall the famous undecidable halting problem language of Turing machines: as this is a single language, there is clearly some bound on the number of conditional rules that is necessary to generate this with a semi-conditional grammar, say, with degree $(2, 1)$ and six nonterminals. As there do exist unary non-recursive languages, also the term $| T |$ does not matter too much if we are concerned about describing undecidable languages with small resources.

Table 2

Survey on nonterminal complexity records for simple SCGs.

Degree $(i, j)$	# Nonterminals	# Conditional Rules	Reference
(2,1)	9	8	[9, Thm. 3.1]
(3,1)	7	7	[9, Thm. 3.2]
(4,1)	7	6	[9, Thm. 3.3]
(4,1)	6	8	[9, Thm. 3.4]

Table 2 lists the current nonterminal complexity records for the simple SCG variation, showing that this syntactical restriction gives rise to further resource requirements to represent all RE languages. from SCG requirements to represent RE languages. This table also raises the interesting question if one could find a way to represent RE with less than five nonterminals in general SCG when increasing the degree to $(4, 1)$ or bigger.

In order to show our results, we make use of several normal forms for type-0 grammars that were presented in [12]. This is somehow special, as previously (mostly) the normal form with non-context-free deletion rules $A B \to λ$ and $C D \to λ$ was used. We also derive several useful properties of the said normal forms and we use them later while proving our results.

This paper is an enhanced version of the previous conference paper that appeared in the proceedings of CiE 2018; see [8]. In comparison with the conference version, here we present full proofs as well as further discussions of our results that had to be suppressed in the conference version due to page length constraints.

2. Preliminaries and definitions

It is assumed in this paper that the reader is familiar with the fundamentals of language theory and mathematics in general. Let $N$ denote the set of non-negative integers. Let $Σ^{*}$ denote the free monoid generated by a finite set Σ (called alphabet) under an operation termed concatenation, where λ denotes the unit of $Σ^{*}$ , also called the empty string. Any element x of $Σ^{*}$ is called a word or string (over Σ) and $x^{R}$ is the reversal of the string x, reading it in reversed order. Any subset of $Σ^{*}$ is called a language. A word v is a subword of $x \in Σ^{*}$ if there are words u, w such that $x = u v w$ . Let $s u b (x) \subseteq Σ^{*}$ denote the set of all subwords of $x \in Σ^{*}$ . Clearly, $s u b (x)$ is a finite language.

2.1. Semi-conditional grammars

Definition 1.
Following [21], a semi-conditional grammar is a quadruple $G = (N, T, P, S)$ , where
N is the nonterminal alphabet,

T is the terminal alphabet $(T \cap N = \emptyset)$ , so that $V = N \cup T$ defines the total alphabet,

$S \in N$ is the start symbol,

P is a finite set of rules of the form $(A \to x, α, β)$ with
$A \in N$ ,

$x \in V^{}$ ,

$α, β \in V^{+} \cup {0}$ , where $0 \notin V$ is a special symbol, intuitively meaning that the condition is missing.

The rule $l : (A \to x, α, β) \in P$ (with l being the label of the rule) is said to be conditional* if $α \neq 0$ or $β \neq 0$ . String α is permitting, while β is forbidden, as formally explained now. The rule labeled l can be applied on a string $u \in V^{} (V ∖ T) V^{}$ if and only if $A \in s u b (u)$ and ( $α \in s u b (u)$ or $α = 0$ ) and ( $β \notin s u b (u)$ or $β = 0$ ). Under these conditions, $u = u_{1} A u_{2}$ will be transformed into $v = u_{1} x u_{2}$ , which is denoted by $u \Rightarrow_{l} v$ .

When no confusion exists on the rule being applied we avoid mentioning the label and we simply write $u \Rightarrow v$ . The language of G is defined as
$L (G) = {w \in T^{} ∣ S \Rightarrow^{} w},$
where $\Rightarrow^{}$ denotes the reflexive and transitive closure of ⇒. Definition 2.
A semi-conditional grammar $G = (N, T, P, S)$ is said to be of degree* $(i, j)$ , where $i, j \in N$ , if in every rule $(A \to x, α, β)$ of P we have $| α | ⩽ i$ and $| β | ⩽ j$ whenever $α, β \neq 0$ . It is termed simple if every rule has at most one non-empty condition. Formally, a semi-conditional grammar G is simple if $(A \to x, α, β) \in P$ implies $0 \in {α, β}$ .

2.2. Geffert normal forms

Following traditional notation, a type-0 grammar is a quadruple $G = (N, T, P, S)$ , where N is the nonterminal alphabet, T is the terminal alphabet, P is the finite set of rules of the form $α \to β$ , where $α \in (N \cup T)^{*} N (N \cup T)^{*}$ and $β \in (N \cup T)^{*}$ , and $S \in N$ .

In [12], quite a number of normal forms for type-0 grammars have been derived. They all differ by the number of nonterminals that are used and also by the number of non-context-free rules. We will hence speak of $(n, r)$ -GNF to refer to a Geffert normal form with n nonterminals and r non-context-free rules. However, all these normal forms characterize the class RE.

The best known such normal form is the $(5, 2)$ -GNF with nonterminals S (the start symbol) and A, B, C, D that uses context-free rules with S as its left-hand side in phase one; in a second phase, non-context-free deletion rules $A B \to λ$ and $C D \to λ$ are applied to finally derive a terminal string. More precisely, in the first phase, in stage one, terminal symbols are produced to the right of the nonterminal S (which is the only nonterminal used in left-hand sides of rules in the first phase) and codifications thereof (using the alphabet ${A, C}$ ) are produced to the left of S at the same time. Then, in stage two of the first phase, strings over ${A, C}$ are produced to the left of S while strings over ${B, D}$ are produced to the right of S, in a sense coding a correct derivation process. Phase 1 ends by replacing S by λ or by $u v$ . Phase 2 then checks the correctness of all guesses from the first phase. More details on the behavior of Geffert normal form grammars can be found in the next section.

In [12], it was also proved that every recursively enumerable language is generated by a type-0 grammar $G = (N, T, P, S)$ with three nonterminals only, i.e., $N = {S, A, B}$ is the set of nonterminals, T is the set of terminal symbols, S is the start symbol and P contains the context-free rules of the form $(i)$ $S \to w$ and the only non-context-free rule of the form $(i i)$ $ABBBA \to λ$ . We therefore call this $(3, 1)$ -GNF for short. Another variant of GNF uses four nonterminals S, A, B, C and two non-context-free rules $A B \to λ$ , $C C \to λ$ and will be called $(4, 2)$ -GNF in this paper.

3. Properties of $(3, 1)$ -GNF and $(4, 2)$ -GNF

We need the following properties of $(3, 1)$ -GNF that follow from its construction from the better-known $(5, 2)$ -GNF with nonterminals S, A, B, C, D; the rules of this normal form are transformed by applying the morphism $A \mapsto A B$ , $B \mapsto B B A$ , $C \mapsto A B B$ and $D \mapsto B A$ (otherwise behaving like the identity) to obtain a grammar in $(3, 1)$ -GNF. So, let $G = ({S, A, B}, T, P, S)$ be a type-0 grammar in $(3, 1)$ -GNF. Then, the following properties are true, as they mostly follow from what is well known about $(5, 2)$ -GNF.

(1)
If $S \Rightarrow^{} w$ , then $w \in {A B, A B B}^{} {S, λ} {B A, B B A}^{} T^{}$ .3
(2)
No sentential form w that is derivable in G contains a substring $BBBBB$ .
(3)
If $S \Rightarrow^{} w$ , then w contains at most one of the three substrings $ABBBA$ or $A B B A$ or $ABBBBA$ , called the central part. In the latter two cases, the derivation is stuck and only the former case will yield a fruitful derivation. The central parts $ABBBA$ , $A B B A$ or $ABBBBA$ are necessarily in the position where (in phase one) the start symbol S was sitting.
(4)
If $S \Rightarrow^{} w$ and w contains no substring $B B B$ , then either $w \in T^{}$ or there is no way to terminate this derivation.
(5)
A derivation $S \Rightarrow^{} x$ with $x \in T^{}$ works in two phases. Phase 1 actually splits in two stages. In the first stage, rules of the form $S \to u S a$ are applied, with $u \in {A B, A B B}^{}$ and $a \in T$ , while in the second stage, rules of the form $S \to u S v$ are applied, where $u \in {A B, A B B}^{}$ and $v \in {B A, B B A}^{}$ , with $u v \neq λ$ . The first phase ends with applying a rule of the form $S \to u v$ , where u, v are as in the previous phrase. In phase two, the deletion rule $ABBBA \to λ$ is applied.
(6)
In view of Property 1, we can assume that in any sentential form that is derivable according to G, there is a symbol X occurring immediately to the right of a substring $ABBBA$ and X will satisfy $X \in T \cup {B}$ .
Remark 2.
We collect all rules $S \to w$ with $S \notin s u b (w)$ plus the only rule $S \to u S$ within $P_{c f}$ , and we can do this for any form of Geffert normal form grammar that we discuss. This set of rules is also contained in Table 1. The reason of this definition will become clear in the proofs of the correctness of the simulations that we introduce next. But the intuition behind this definition of $P_{c f}$ can be understood already at this point. We have to stop malicious derivations that are possible when ‘restarting’ the simulation of Phase 1 within the already started simulation of Phase 2, which is potentially possible, as we like to re-use the nonterminal S in the simulation of Phase 2. But even if this unintended, malicious simulation could start, at some point rules from $P_{c f}$ must be applied in order to be able to derive a terminal string. It is therefore sufficient to block this malicious derivation by disabling the simulation of any rule from $P_{c f}$ . This also explains why the cardinality of $P_{c f}$ enters Table 1.

To give an example how most properties easily follow from what is known about the Geffert normal form using $A B \to λ$ and $C D \to λ$ as deletion rules or can be shown by a simple direct induction argument for $(3, 1)$ -GNF, consider the first property. As it is easily observed by the rules $S \to u S v$ or $S \to u v$ with $u \in {A, C}^{}$ and $v \in {B, D}^{} \cup T$ , any sentential form in such a grammar is element of ${A, C}^{} {S, λ} ({B, D}^{} \cup T)^{}$ , and looking a bit closer, even of ${A, C}^{} {S, λ} {B, D}^{} T^{}$ . The morphism described above yields the claim for $(3, 1)$ -GNF.

The last property of $(3, 1)$ -GNF needs some further explanation. If $λ \notin L (G)$ , then the claim follows with Property 1. If $λ \in L (G)$ , then there might be no X (immediately) to the right of $ABBBA$ at all. We fix this as follows. If $λ \in L (G)$ , we consider a $(3, 1)$ -GNF grammar for $L ∖ {λ}$ (with start symbol S) and add the rule $S \to λ$ to it. Notice that the grammar constructed by Geffert contains rules of the form $S \to u S v$ if and only if it contains rules of the form $S \to u v$ , and the mentioned rules are the only ones involving S, so that this additional rule does not harm Geffert’s construction.

We shall now consider the properties of another normal form $(4, 2)$ -GNF whose non-context-free rules are $A B \to λ$ , $C C \to λ$ . This normal form can be obtained from $(5, 2)$ -GNF with the morphism $A \mapsto C A A$ , $B \mapsto B B C$ , $C \mapsto C A$ and $D \mapsto B C$ .
(1)
If $S \Rightarrow^{} w$ , then $w \in {C A, C A A}^{} {S, C C, λ} {B C, B B C}^{} T^{}$ .4
(2)
No sentential form derivable in the grammar contains any of the substrings $B A$ , $A A A$ , $B B B$ , $C C C$ . Also substrings of the form $B {B, C, S}^{} A$ are not possible (in other words, after the occurrence of B, then A is not possible to occur in the sentential form).
(3)
If $S \Rightarrow^{} w$ , then w contains at most one of the two substrings $C C$ , $A B$ (called the central part) at most once. This also rules out $A B C C$ and $A B A B$ as substrings of sentential forms.
(4)
Again, the derivation proceeds in two phases, the first one split into two stages. Only in phase two, the central part (either $A B$ or $C C$ ) will appear.
(5)
If at some point in the second phase, the intended central part (either $A B$ or $C C$ ) disappears and instead either $A C$ or $B C$ shows up in the center (notice that these strings can always show up to the left or to the right of the central part), then the derivation is blocked.

All these claims can be seen by reviewing corresponding results on the basic $(5, 2)$ -GNF and observing the effect of the described codings. Let us explain how to see these properties (that we will make use of in the constructions and simulations throughout this paper) further.

We carefully walk through the construction described in [12]. Geffert did not start with a characterization of RE by grammars or Turing machines, but rather by pairs of morphisms. Namely, as a first step (Theorem 1), it is shown (referring to [11]) that each RE language $L \subseteq Σ^{}$ can be represented by morphisms $h_{1}, h_{2} : Σ_{A}^{} \to Σ_{B}^{}$ , where $Σ_{A}$ and $Σ_{B}$ are some carefully chosen alphabets satisfying $Σ_{B} \supseteq Σ$ , with
$L = {w \in Σ^{} ∣ \exists α \in Σ_{A}^{+} : h_{2} (α) = h_{1} (α) w} .$
Looking at the proof, it becomes clear that $h_{1}$ is not erasing, while $h_{2}$ is erasing, i.e., there is some $x \in Σ_{A}$ such that $h_{2} (x) = λ$ .

This theorem is used to prove that each RE language can be represented by some Extended Post Correspondence Problem (EPC), yielding Theorem 2. An instance P of EPC is given by a set of r pairs of binary strings $(u_{i}, v_{i})$ , with $1 ⩽ i ⩽ r$ , and some binary string $z_{a}$ for each symbol $a \in Σ$ . Then,
$L (P) = {x_{1} \dots x_{n} \in Σ^{} ∣ \exists s_{1}, \dots, s_{l} \in [1 \dots r] : v_{s_{1}} \dots v_{s_{l}} = u_{s_{1}} \dots u_{s_{l}} z_{x_{1}} \dots z_{x_{n}}} .$
The proof of Theorem 2 makes use of Theorem 1 by using unambiguous binary block encodings c of the letters in $Σ_{B}$ . Then, $r = | Σ_{A} |$ many pairs are created by setting $u_{i} = c (h_{1} (e_{i}))$ and $v_{i} = c (h_{2} (e_{i}))$ for the ith letter $e_{i} \in Σ_{A}$ . Similarly, for each $a \in Σ \subseteq Σ_{B}$ , we set $z_{a} = c (a)$ . Notice that none of the $u_{i}$ constructed in this way is empty, while exactly one $v_{i}$ equals λ. Also, none of the $z_{a}$ is empty.

Such an EPC P is then used to show the well-known GNF results. For instance, for the normal form having rules $A B \to λ$ and $C D \to λ$ , one uses the morphisms $g_{1} : {0, 1}^{} \to {A, C}^{}$ with $g_{1} (0) = A$ and $g_{1} (1) = C$ , as well as $g_{2} : {0, 1}^{} \to {B, D}^{}$ with $g_{2} (0) = B$ and $g_{2} (1) = D$ . Then, add rules $S \to g_{1} (z_{a}^{R}) S a$ for $a \in Σ$ and rules $S \to g_{1} (u_{i}^{R}) S g_{2} (v_{i})$ , $S \to g_{1} (u_{i}^{R}) g_{2} (v_{i})$ for $1 ⩽ i ⩽ r$ . Whenever one starts using any of the rules $S \to x$ (and none of the non-context-free deletion rules), some non-empty word over ${A, C}$ will be present, and if S is in the sentential form, this word will be to the left of S. Moreover, there is exactly one rule of the form $S \to u S$ for some $u \in {A, C}^{+}$ . Returning to Footnote 3, it is clear that the sub-phases applying rules of the form $S \to g_{1} (z_{a}^{R}) S a$ and of the form $S \to g_{1} (u_{i}^{R}) S g_{2} (v_{i})$ can get mixed, but in that case, Geffert could prove that a resulting sentential form cannot derive a terminal string. Similar remarks are true for the other GNFs, as they only differ in the encodings.

For instance, we obtain the $(4, 2)$ -GNF by re-defining $g_{1} : {0, 1}^{} \to {A, C}^{}$ as $g_{1} (0) = C A A$ and $g_{1} (1) = C A$ , as well as $g_{2} : {0, 1}^{} \to {B, C}^{}$ by setting $g_{2} (0) = B B C$ and $g_{2} (1) = B C$ . Again, whenever one starts using any of the rules $S \to x$ (and none of the non-context-free deletion rules), some non-empty word over ${A, C}$ will be present, and if S is in the sentential form, this word will be to the left of S. Moreover, there is exactly one rule of the form $S \to u S$ for some $u \in {A, C}^{+}$ .

For $(3, 1)$ -GNF, we take $g_{1} : {0, 1}^{} \to {A, B}^{}$ as $g_{1} (0) = A B B$ and $g_{1} (1) = A B$ , as well as $g_{2} : {0, 1}^{} \to {A, B}^{*}$ with $g_{2} (0) = B A$ and $g_{2} (1) = B B A$ . Whenever one starts using any of the rules $S \to x$ (and none of the non-context-free deletion rules), some word from ${A B B, A B}^{+}$ will be present, and if S is in the sentential form, this word will be to the left of S. Moreover, there is exactly one rule of the form $S \to u S$ for some $u \in {A B B, A B}^{+}$ .

Figure 1.
Semi-conditional rules with 6 nonterminals simulating $A B \to λ$ and $C C \to λ$ and $S \to w \in P_{c f}$ .
4. Main results

In this section, the main results of this paper (as collected in Table 1) are presented and proved. Recall that all these results show that even under rather strict bounds on the descriptional complexity of semi-conditional grammars, all recursively enumerable languages can be generated. The proofs are all based on simulating type-0 grammars that are obeying some variants of Geffert normal forms, which are known to characterize the recursively enumerable languages as explained in the previous section.

In all simulations, it could happen that sentential forms are derived in the simulating grammar by using context-free rules only that consist of a mixture of nonterminals and terminals (not necessarily the terminals are at the end of the derived string), see Footnote 3. However, one can easily observe for each of the simulating grammars that the derivation will finally be stuck. Therefore, we do not discuss this case in details for each simulation separately.

In the next theorem, we employ the daring and novel idea of reusing the nonterminal S back in the derivation while simulating Phase 2 of the GNF grammar derivation with the aim to further reduce the number of nonterminals, but at the cost of more conditional rules, because (having S is present again) we need to avoid unintended ‘restarts’ of the simulation, see Remark 2.

Theorem 1.
For each recursively enumerable language L, there is a semi-conditional grammar of degree $(2, 1)$ with only six nonterminals that describes L.
Proof.
Consider some recursively enumerable language L represented by some type-0 grammar
$G = ({S, A, B, C}, T, P, S)$
in $(4, 2)$ -GNF. G is simulated by a semi-conditional grammar $G^{'} = (N, T, P^{'}, S)$ of degree $(2, 1)$ , where $N = {S, A, B, C, $, #}$ .

The particular non-context-free deletion rules $A B \to λ$ and $C C \to λ$ of G are simulated by the semi-conditional rules given in Fig. 1 where the last rule is considered for each context-free rule $S \to w$ of G.

The intended derivations of phase one of G can be simulated by literally the same rules (where only the forbidden context $ was added that has no influence here as $ is not present until end of phase one). Observe that it is not possible to start such a simulation when still being in the phase one simulation, as $A B$ or $C C$ must be present as a substring, which can only happen after finishing with the simulation of phase one. The transition from phase one to phase two is done by (simulating) a rule of the form $S \to w$ with $S \notin s u b (w)$ .

In phase two, we consider a sentential form $u v t$ , where $u \in {C A, C A A}^{}$ , $v \in {B C, B B C}^{}$ and $t \in T^{}$ with $S \Rightarrow^{} u v t$ . If u ends with A and v starts with B, i.e., $u = u^{'} A$ and $v = B v^{'}$ , $A B \to λ$ can be applied. In the simulating semi-conditional grammar, we find
$u v t = u^{'} A B v^{'} t \Rightarrow_{1} u^{'} $ S B v^{'} t \Rightarrow_{2} u^{'} $ S # v^{'} t \Rightarrow_{3} u^{'} $ $ # v^{'} t \Rightarrow_{6}^{2} u^{'} # v^{'} t \Rightarrow_{7} u^{'} v^{'} t .$
If instead $C C$ is a substring of the current sentential form $u v t$ , this means that $u = u^{'} C$ and $v = C v^{'}$ , and now $C C \to λ$ is simulated as follows:
$u v t = u^{'} C C v^{'} t \Rightarrow_{4} u^{'} $ $ C v^{'} t \Rightarrow_{5} u^{'} $ $ # v^{'} t \Rightarrow_{6}^{2} u^{'} # v^{'} t \Rightarrow_{7} u^{'} v^{'} t .$
By induction, this argument shows that $L (G) \subseteq L (G^{'})$ .

Conversely, consider a sentential form w derivable by the simulating grammar $G^{'}$ that is also derivable by the $(4, 2)$ -GNF grammar G. Assume first that w contains some occurrence of S. As w is derivable in G, neither $ nor # occur in w only rules of the type $(S \to x, 0, β)$ apply, $β \in {0, $}$ . In particular, Rule 3 is not applicable. Hence, for the string $w^{'}$ derivable from w in one step we also find $w \Rightarrow_{G} w^{'}$ . This means that we are simulating phase one of G faithfully with $G^{'}$ .

We are left with the case that w does not contain S. As w is also derivable in G, we are in (the simulation of) phase two. Still, w does not contain any occurrences of $ and # either. If w is a terminal string, nothing remains to be shown. So, w contains some occurrences from ${A, B, C}$ and satisfies Property 1 of $(4, 2)$ -GNF. Hence, $w \in {C A, C A A}^{} {S, C C, λ} {B C, B B C}^{} T^{}$ . All rules but Rule 1 and Rule 4 require that $s u b (w) \cap {S, #, $} \neq \emptyset$ . If the central part $A B$ is a substring of w, then Rule 1 applies, starting an intended simulation cycle as discussed above. We will look into this intended derivation later.

If $A B$ is a substring of w, then $w = u^{'} A B v^{'} t$ , with $u^{'} \in {C A, C A A}^{} {C, C A}$ , $v^{'} \in {C, B C} {B C, B B C}^{}$ and $t \in T^{}$ (by induction), so that only Rule 1 is applicable. This leads us to $w_{1}$ , replacing any occurrence of A by $$ S$ . As ${#, $ $} \cap s u b (w_{1}) = \emptyset$ , only Rule 2 is applicable on $w_{1}$ . The resulting string $w_{2}$ is obtained from $w_{1}$ by replacing some occurrence of B by #. As $$, #, S \in s u b (w_{2})$ , only Rules 3 or 6 apply. As $w_{2}$ will have S occurring to the right of the only occurrence of $, Rule 6 cannot be applied, leaving us with Rule 3 as the only possibility. In order to have $S # \in s u b (w_{2})$ , $w_{2} = u^{'} $ S # v^{'} t$ is enforced due to Properties 2 and 3 of $(4, 2)$ -GNF, as there are no other occurrences of the substring $A B$ in w but the one that we singled out. Hence, with $w_{2} \Rightarrow w_{3}$ , we know that $w_{3} = u^{'} $ $ # v^{'} t$ . Due to the forbidden contexts and due to the absence of subword $A B$ or $C C$ , only Rules 3 or 6 might apply, with Rule 3 being disabled, as $S \notin s u b (w_{3})$ . In order to apply Rule 6, $$ # \in s u b (w_{3})$ is required. Hence, $w_{3} \Rightarrow_{6}^{2} w_{4} = u^{'} # v^{'} t$ follows, as the arguments on the intermediate sentential form $u^{'} $ # v^{'} t$ are the same. As $S \notin s u b (w_{4})$ , Rules 1, 2, 3 are not applicable (and of course, no rule from phase one). As $$ \notin s u b (w_{4})$ , Rules 5 and 6 do not apply, either. Hence, we are left with either applying Rule 4 or Rule 7 next. However, applying Rule 4 would require $C C$ to appear as a substring in $w_{4}$ , which would mean that $C C$ appears twice as a substring in w, contradicting Properties 2 and 3 of $(4, 2)$ -GNF. Confer our definitions of $u^{'}$ and $v^{'}$ at the beginning of this paragraph. Rule 7 would be the intended rule to be applied on $w_{4}$ , leading us to some $w^{'}$ that satisfies $w \Rightarrow_{G} w^{'}$ by applying the rule $A B \to λ$ from G, this way finishing our argument in this case.

The argument for the case that $C C$ is a substring of w is along similar lines. If $C C$ is a substring of w, then $w = uCCvt$ , with $u \in {C A, C A A}^{}$ , $v \in {B C, B B C}^{}$ and $t \in T^{}$ (by induction), so that only Rule 4 is applicable. We arrive at a string $w_{1}$ where some occurrence of C has been replaced by $$ $$ . By the structure of $w_{1}$ , only Rule 5 is applicable now, replacing some other occurrence of C by #, leading to a string $w_{2}$ . Due to the forbidden contexts and due to the absence of subword $A B$ or $C C$ , only Rules 3 or 6 might apply, with Rule 3 being disabled, as $S \notin s u b (w_{2})$ . In order to apply Rule 6, $$ # \in s u b (w_{2})$ is required. This situation is only possible if $w_{1} = u $ $ C v t$ and $w_{2} = u $ $ # v t$ . So, with $w_{2} \Rightarrow w_{3}$ , we are forced to $w_{3} = u $ # v t$ . The argument continues as in the previous case, as the u, v discussed here are also possible as $u^{'}$ , $v^{'}$ discussed previously.

We can also rule out using rules $(S \to x, 0, 0)$ . We might attempt to use some rules $(S \to x, 0, β)$ with $β \in {0, $}$ when facing $w_{1}$ (obtained from $w = u^{'} A B v^{'} t$ by replacing one occurrence of A by $$ S$ ) or $w_{2} = u^{'} $ S # v^{'} t$ . In both cases, $ occurs, ruling out the application of rules $(S \to x, 0, $)$ . But this means by definition of $P_{c f}$ that $S \in s u b (x)$ for all rules $(S \to x, 0, 0)$ that are applicable to $w_{1}$ or to $w_{2}$ .

However, if we attempt to err from $w_{1}$ , then some string from ${C A, C A A}^{+}$ will be created to the left of S. This prevents Rule 2 from being (ever) applied and hence there is no way to get rid of $ again by applying Rule 6. But this is the prerequesite to (ever) delete S, because surely there is no # to the right of S, disabling Rule 3. Hence, this derivation can never terminate.

If we try to start using the context-free rule simulations from $w_{2}$ on, we might be tempted to create a non-empty string from ${A B, A B B}^{+}$ before applying Rule 3. This would give us (to mention the shortest possibility) $w^{'} = u^{'} $ A B $ # v^{'} t$ , which would actually allow us to have an unwanted terminating derivation. This case is therefore stopped by having the only rule of the form $S \to u S$ in G (that is responsible for this unwanted derivation) to be guarded in $G^{'}$ by putting $(S \to \bar{u} S, 0, $)$ into its rule set, as $S \to \bar{u} S \in P_{c f}$ .

By induction, we see that $L (G^{'}) \subseteq L (G)$ .

By replacing the use of symbol S by a new nonterminal $†$ , we can avoid using an unbounded number of conditional rules. This would yield a result nearly matching the one of Okubo [20].

It is open if the number of nonterminals can be further reduced for semi-conditional grammars of degree $(2, 1)$ . In the following result, we show that if we increase the (maximum) forbidden context length from one to two, then with 6 conditional rules and 6 nonterminals we can obtain a computational completeness result. Notice that we are not aware of any previous similar results for semi-conditional grammars of degree $(i, 2)$ for any i.

Figure 2.
Semi-conditional rules with 6 nonterminals for simulating $A B \to λ$ and $C C \to λ$ .
Theorem 2.
For each recursively enumerable language L, there is a semi-conditional grammar of degree* $(2, 2)$ with only six nonterminals and six conditional rules that describes L.
Proof.
Consider some RE language L represented by some type-0 grammar
$G = ({S, A, B, C}, T, P, S)$
in $(4, 2)$ -GNF. G is simulated by a semi-conditional grammar $G^{'} = (N, T, P^{'}, S)$ of degree $(2, 2)$ , where $N = {S, A, B, C, $, #}$ .

The particular non-context-free deletion rules $A B \to λ$ and $C C \to λ$ of G are simulated by the semi-conditional rules given in Fig. 2. The idea behind the construction of the conditional rules of $G^{'}$ as follows. Recall that a typical sentential form in phase two of a grammar in $(4, 2)$ -GNF consists of a prefix from ${C A, C A A}^{}$ , followed by either $A B$ or $C C$ , followed in turn by an infix from ${B C, B B C}^{}$ ; the string terminates with a suffix from $T^{}$ . The central parts $A B$ and $C C$ are encoded as $$ #$ and $# $ # #$ , respectively. More specifically, the A in $A B$ is encoded by $ and the B is encoded by #, using Rules 1 and 2. The negative conditions of these rules avoid applying them repeatedly. Similarly, in the central part $C C$ , the first C is changed to $# $$ and the second C is changed into $# #$ , using Rules 3 and 4. When a subword $$ #$ is present in the string, then it means that $A B$ or $C C$ are encoded properly and therefore the markers $ and # can be deleted, using Rules 5 and 6. Malicious derivations are avoided with the following strategies. (a) As Rule 3 introduces $# $$ , its application cannot be followed by applying Rule 2 due to the forbidding condition of Rule 3. (b) The positive condition in Rule 4 avoids applying Rule 3 on the second C of the central part or anywhere in the non-central part and Rule 4 afterwards. (c) One other possibility is that a substring $A C$ can also be encoded to $$ # #$ when a substring $A B$ is also present in the string (by Rules 1 and 4). However, in that case, the central part $A B$ is untouched and the negative condition in Rule 5 stops the encoded $A C$ to vanish.

We now explain how the simulation of G by $G^{'}$ should work. The intended derivations of phase one of G can be simulated by literally the same rules of G, as these rules appear in $G^{'}$ , as well. In phase two, we consider a sentential form $u v t$ , where $u \in {C A, C A A}^{}$ , $v \in {B C, B B C}^{}$ and $t \in T^{}$ with $S \Rightarrow^{} u v t$ . If u ends with A and v starts with B, i.e., $u = u^{'} A$ and $v = B v^{'}$ , $A B \to λ$ can be applied. In the simulating semi-conditional grammar, we find
$u v t = u^{'} A B v^{'} t \Rightarrow_{1} u^{'} $ B v^{'} t \Rightarrow_{2} u^{'} $ # v^{'} t \Rightarrow_{5} u^{'} # v^{'} t \Rightarrow_{6} u^{'} v^{'} t .$
If instead $C C$ is a substring of the current sentential form $u v t$ , this means that $u = u^{'} C$ and $v = C v^{'}$ , and now $C C \to λ$ is simulated as follows:
$u v t = u^{'} C C v^{'} t \Rightarrow_{3} u^{'} # $ C v^{'} t \Rightarrow_{4} u^{'} # $ # # v^{'} t \Rightarrow_{5} u^{'} # # # v^{'} t \Rightarrow_{6}^{3} u^{'} v^{'} t .$
By induction, this argument shows that $L (G) \subseteq L (G^{'})$ .

To prove the converse part, by induction, we can assume that we consider a string w derivable from S in $G^{'}$ that is also derivable from S in G. In particular, none of the nonterminals $ and # occurs in w. We are going to argue that after some further derivation steps of $G^{'}$ (starting from w), either the derivation is stuck, or some string is produced that is also derivable from S in G. By induction, this shows $L (G^{'}) \subseteq L (G)$ .

Assume that $w \Rightarrow w^{'}$ in $G^{'}$ , using one of the unconditional rules in $G^{'}$ . As these unconditional rules correspond to the context-free rules of G, $w \Rightarrow w^{'}$ is also valid in G.

Hence, we are left with a situation where we apply a conditional rule to w. By the nature of the positive conditions, only Rules 1 and 3 are possibly applicable. Hence, ${A B, C C} \cap s u b (w) \neq \emptyset$ . As $S \Rightarrow^{} w$ in G, w belongs to phase two of the $(4, 2)$ -GNF grammar G. According to Property 1 of $(4, 2)$ -GNF discussed above, the interesting cases that remain to be discussed is when (i) $w = u v t$ , or (ii) $w = uCCvt$ , with $u \in {C A, C A A}^{}$ , $v \in {B C, B B C}^{}$ and $t \in T^{}$ .

Case (i): Clearly, if $u = v = λ$ , we are ready, as a terminal string is already derived. Assume $w = u^{'} A B v^{'} t$ with $u^{'} \in {C A, C A A}^{} {C, C A}$ and $v^{'} \in {C, B C} {B C, B B C}^{}$ . Now, only Rule 1 is applicable. This leads us to $w_{1}$ , replacing some occurrence of A by $ and Rule 1 cannot be applied again until $ is deleted (and $A B$ is present). As ${#, C C} \cap s u b (w_{1}) = \emptyset$ , only Rule 2 and Rule 4 are applicable on $w_{1}$ . If Rule 4 is applied, this means that the A that was changed to $ was immediate left of some C and therefore the A in the substring $A B$ is still untouched. In that case, the derivation stucks-up as no rule is applicable anymore including Rule 5 (as $A B$ is a forbidden context and is still present in the string). So, only Rule 2 is possible to apply to $w_{1}$ . If Rule 2 is applied, then the string $w_{2} = u^{'} $ # v^{'} t$ results. As ${$, #} \subset s u b (w_{2})$ , only Rule 4 and Rule 5 are possibly applicable. As $$ C \notin s u b (w_{2})$ , Rule 4 is not applicable. So, after applying Rule 5, we get the resultant string $w_{3} = u^{'} # v^{'} t$ . As ${A B, C C} \cap s u b (w_{3}) = \emptyset$ , neither Rule 1 nor Rule 3 are applicable and the only applicable rule is Rule 6 which derives the desired string $w_{4} = u^{'} v^{'} t$ .

Case (ii): Assume $w = uCCvt$ with $u \in {C A, C A A}^{}$ , $v \in {B C, B B C}$ and $t \in T^{}$ . As $A B$ is not present in the string, Rule 1 cannot be applied. The only applicable rule is Rule 3. Consider $w \Rightarrow_{3} w_{1}$ . Comparing $w_{1}$ with w, some occurrence of C has been replaced by $# $$ . We discuss three sub-cases in the following.

(a) If Rule 3 has been applied to the second C of the substring $C C$ , then $C # $ \in s u b (w_{1})$ . As # is present in the string $w_{1}$ , Rules 2 and 3 cannot be applied. As $ is present in the string, Rules 1 and 6 also cannot be applied. By the second property of $(4, 2)$ -GNF, w (and hence $w_{1}$ ) does not contain $C C C$ as a substring. Hence, the permitting context $$ C$ of Rule 4 is not a substring of $w_{1}$ , so that Rule 4 cannot be applied. Neither is the permitting context $$ #$ of Rule 5 available in $w_{1}$ . As none of the rules can be applied, the derivation gets stuck.

(b) If any C not belonging to the substring $C C$ is replaced by $# $$ , then ${C C, # $} \subset s u b (w_{1})$ . By the forbidden contexts, Rules 1, 2, 3, 6 cannot be applied. As before, the presence of the substring $$ C$ in $w_{1}$ would presuppose the presence of a second substring $C C$ in w, which is impossible by the structure of w, so that Rule 4 is not applicable. Finally, $$ # \notin s u b (w_{1})$ , disabling the application of Rule 5.

(c) Hence, the only possibility is that the first C in the substring $C C$ was changed to $# $$ (by Rule 3). Hence, $w_{1} = u # $ C v t$ must hold. A case analysis similar to the previous ones proves that now, the only applicable rule is Rule 4. On applying it to the string $w_{1}$ , some occurrence of C is replaced by $# #$ , yielding $w_{2}$ . Two further sub-cases arise. (c1) Assume that some C that is not next to $# $$ is changed. According to the second property of $(4, 2)$ -GNF, $C C C$ is not present in the string. Then, $# $ C$ remains as a substring in $w_{2}$ . Though $$ C$ is a substring of $w_{2}$ and is a permitting context of Rule 4, we cannot apply Rule 4 as $# # \in s u b (w_{2})$ . (c2) Therefore, Rule 4 is applied only to the second C of $C C$ . Thus, $w_{2} = u # $ # # v t$ . Now the only applicable rule to $w_{2}$ is Rule 5 and applying it we get $w_{3} = u # # # v t$ . As $A B$ is still not a substring of $w_{3}$ , Rule 1 cannot be applied and the only applicable rule is Rule 6. Applying it three times produces the desired string $u v t$ .

By an induction argument, we see that $L (G^{'}) \subseteq L (G)$ .

Aiming at further trade-off results, trading the number of nonterminals for degree conditions, we consider semi-conditional grammars of degree $(3, 1)$ . In [20], Okubo has shown that seven nonterminals with degree $(2, 1)$ suffice to describe any RE language. No genuine results for degree $(3, 1)$ are given in the literature. Finally, we improve on the nonterminal number by reusing the nonterminal S again, but with degree $(3, 1)$ and of more conditional rules.
Theorem 3.
For each recursively enumerable language L, there is a semi-conditional grammar of degree* $(3, 1)$ with only five nonterminals that describes L.
Proof.
We start out with a representation of a recursively enumerable language by a type-0 grammar $G = (N, T, P, S)$ in $(3, 1)$ -GNF that has only three nonterminals S, A, B. We are going to construct an equivalent a semi-conditional grammar of degree $(3, 1)$ $G^{'}$ with additional nonterminals $ and #. G has context-free rules of the form $S \to w$ that we simply also incorporate in the semi-conditional grammar $G^{'}$ that we produce without any conditions (apart from the rules that replace S by a terminal string), plus one non-context-free deletion rule, namely $ABBBA \to λ$ . This particular rule is simulated by the semi-conditional rules listed in Fig. 3. The intended simulation is as follows, basically executing the given rules in order.
$\begin{aligned} A B B B A X & \Rightarrow_{1} A B $ B A X \Rightarrow_{2} A # $ B A X \Rightarrow_{3. B} A # B A X \Rightarrow_{4} A # S $ A X \\ \Rightarrow_{δ S} A # $ A X \Rightarrow_{3. A} A # A X \Rightarrow_{5} $ $ # A X \Rightarrow_{6} $ $ A X \Rightarrow_{7} $ $ # X \Rightarrow_{8. X} $ # X \Rightarrow_{8. X} # X \Rightarrow_{9. X} X \end{aligned}$
(1)

Figure 3.
Semi-conditional rules with 5 nonterminals for simulating $ABBBA \to λ$ , with $X \in T \cup {B}$ , and for simulating $S \to w \in P_{c f}$ .

Notice that we might assume that in any sentential form that is derivable according to G, a symbol X occurs to the right of the substring $ABBBA$ that satisfies $X \in T \cup {B}$ according to the last $(3, 1)$ -GNF property. So, we can assume that the symbol X that we are testing in Rules $8. X$ and $9. X$ does exist. This shows that $L (G) \subseteq L (G^{'})$ . Before we continue with proving the converse inclusion $L (G^{'}) \subseteq L (G)$ , we observe the following. Observation.
If $w \in (T \cup {A, B})^{}$ and if $w \Rightarrow w^{'}$ in $G^{'}$ , then there is only at most one applicable rule in $G^{'}$ , which is Rule 1. Furthermore, this requires that $B B B \in s u b (w)$ .

This claim is easily understood by inspecting the rules listed in Fig. 3, as all other rules require that ${$, #} \cap s u b (w) \neq \emptyset$ . This nicely fits with Property 4 of $(3, 1)$ -GNF grammars.

Now we prove the converse inclusion $L (G^{'}) \subseteq L (G)$ . Consider some sentential form w of $G^{'}$ . By induction, we can assume that w is also a sentential form of G. We are going to argue that after some further derivation steps of $G^{'}$ (starting from w), either the derivation is stuck, or some sentential form is produced that is also a valid sentential form of G. By induction, this shows $L (G^{'}) \subseteq L (G)$ .

As assumed above, w is a valid sentential form in G also, so it is possibly part of a derivation taking place in phase one in this $(3, 1)$ -GNF grammar only. Hence, only context-free rules have been used, and this could be also assumed with $G^{'}$ , i.e., the simulation was the intended one. In particular, none of the nonterminals S, $, # occurs in the sentential form w at the end of the simulation of phase one.

Hence, we are now in phase two of the $(3, 1)$ -GNF grammar. According to the properties of $(3, 1)$ -GNF listed above, the interesting cases that remain to be discussed is when (i) $w = uABBBAvt$ or (ii) $w = uABBBBAvt$ or (iii) $w = uABBAvt$ with $u \in {A B, A B B}^{}$ , $v \in {B A, B B A}^{}$ , where in the latter two cases (ii) and (iii), there is no way to terminate the derivation in G according to Properties 3 and 4 of $(3, 1)$ -GNF grammars. According to Property 5 of $(3, 1)$ -GNF grammars, the only rule applicable in G would be the non-context-free deletion rule. In $G^{'}$ , we also find that at most some rules from Figure 3 might apply. By our Observation, Case (iii) is ruled out. In $G^{'}$ , as can be easily checked, the only applicable rule would then be the first rule $B \to $$ . This results in a string $w_{1}$ with $w \Rightarrow w_{1}$ where one occurrence of B is replaced by $. Now, due to the fact that $ is a forbidden context in the first rule, it cannot be applied again. We can check that rules numbered 3, 4, 5, 6, $8. X$ , $9. X$ are not applicable as # is not contained in $w_{1}$ . As $$ $ \notin s u b (w_{1})$ , neither Rule 7 is applicable. So, we have to employ Rule 2. In order to continue, we can conclude that (1) $w_{1} = u A B $ B A v t$ or (2) $w_{1} = u A B $ BBAvt$ or (3) $w_{1} = uABB $ B A v t$ , as in the given normal form grammar G, no strings with a sequence of more than four B’s can be produced, see Property 2 of $(3, 1)$ -GNF grammars, and there is only one position where one could find a sequence of three or four B’s according to Property 3 of $(3, 1)$ -GNF. It is then clear that for $w_{1} \Rightarrow w_{2}$ we have that (a) $w_{2} = u A # $ B A v t$ or (b) $w_{2} = u A B $ # A v t$ (both from $w_{1} = u A B $ B A v t$ ), or (c) $w_{2} = u A # $ BBAvt$ or (d) $w_{2} = u A B $ # B A v t$ or (e) $w_{2} = u A B $ B # A v t$ (all three from $w_{1} = u A B $ BBAvt$ ), or (f) $w_{2} = u A # B $ B A v t$ or (g) $w_{2} = u A B # $ B A v t$ or (h) $w_{2} = uABB $ # A v t$ (all three from $w_{1} = uABB $ B A v t$ ), or (j) any other occurrence of B within u or v is replaced, leading to $w_{2}$ where the subword between the u- and the v-part is identical to $w_{1}$ .

In each case, both $ and # are present in the string $w_{2}$ , which immediately rules out all but Rules 3, 6, $8. X$ due to the forbidden strings in the other rules. Rule 6 requires two occurrences of $, which is not satisfied with any of the variations of $w_{2}$ . We are now discussing possibilities for $w_{2} \Rightarrow w_{3}$ with the remaining Rules $8. X$ and 3.

If we try to apply Rule $8. X$ , this requires the substring $$ # X$ for $X \in T \cup {B}$ , which leaves us with Case (d). In that case, $w_{2} \Rightarrow u A B # B A v t = w_{3}$ . Now, Rule 1 is excluded, as substring $B B B$ is missing; Rule 2 is excluded by the presence of #; Rules 3 and $8. X$ are not possible, as $ is not present; Rule 4 is not applicable, as the substring $A # B$ is not present; similarly, Rule 5 is not applicable, as the substring $A # A$ is missing; Rules 6 and 7 require two occurrences of $ in the string, which is not the case here. Consider now applying Rule $9. X$ , which leads us to $w_{4} = uABBAvt$ . By our Observation, there is no possible continuation of this derivation in $G^{'}$ .

If we want to apply Rule 3 instead to the string $w_{2}$ , which in fact has the same effect as Rule $8. X$ , namely, to delete the only occurrence of $ in $w_{2}$ , this means that $# $ Y \in s u b (w_{2})$ for $Y = A$ or $Y = B$ . This leaves us with Cases (a) or (c) or (g).

In Case (a), we find $w_{2} \Rightarrow_{3} u A # B A v t = w_{3}$ . By carefully looking through all permitting conditions, it becomes clear that only Rules 4 or 9 are applicable. If Rule 9 is applied, we derive $uABAvt$ , and this derivation is stuck due to our Observation. So, $w_{4}$ emerges from $u A # B A v t$ by replacing one occurrence of B by $S $$ . Apart from arriving at $w_{4} = u A # S $ A v t$ , which is in fact the intended simulation, any other occurrence of B might be also replaced. Anyways, as $w_{4}$ contains both $S $$ and #, due to the forbidden conditions, we have to delete S next by using $δ S$ . This way, we check if A is to the right of $S $$ . Hence, we either have $w_{5} = u A # $ A v t$ , which is in fact the intended simulation, or $w_{5} = u^{'} A # B A v^{'} t$ where either $u^{'} = u$ and $v^{'}$ is obtained from v by replacing one occurrence of B left of some occurrence of A by $, or vice versa, interchanging the roles of u and v. In any case, as both # and $ are present, we have to apply one of the Rules 3, 6 or 8 next. Let us look a bit closer. As the symbol left to # is A and as this is the only occurrence of # in $w_{4}$ , Rules 6 and 8 cannot be applied due to the permitting conditions. Rule 3 requires $ sitting next right to #, which enforces $w_{5} = u A # $ A v t$ , so that Rule 3 applies, leading to $w_{6} = u A # A v t$ as intended.

In Case (c), $w_{2} \Rightarrow u A # BBAvt$ , the same argument as in the previous analysis applies, i.e., only Rules 4 or 9 are applicable, with the latter rule leading nowhere due to our Observation. Hence, we arrive at some $w_{4}$ obtained from $u A # BBAvt$ by replacing one occurrence of B by $S $$ . This leads us to three possibilities for $w_{4}$ : $(α)$ $u A # S $ B A v t$ , $(β)$ $u A # B S $ A v t$ , or $(γ)$ $u^{'} A # B B A v^{'} t$ , with either $u = u^{'}$ or $v = v^{'}$ , plus replacing one occurrence of B by $S $$ in $u v$ to get $u^{'} v^{'}$ . As $w_{4}$ contains both $S $$ and #, due to the forbidden conditions, we have to delete S next by using $δ S$ , but this requires $S $ A \in s u b (w_{4})$ , leaving us with Case $(β)$ , which then necessitates $w_{5} = u A # B $ A v t$ . Now, the derivation is finally stuck, as can be verified: as ${#, $} \subseteq s u b (w_{5})$ , one of Rules 3, 6, 8 should be applied, but none of the permitting subwords is present in $w_{5}$ .

In Case (g), $w_{2} \Rightarrow_{3} u A B # B A v t$ . By inspection, it becomes clear that only Rule 9 is applicable, but the resulting string $uABBAvt$ cannot lead to any further sentential form due to our Observation.

Let us therefore return to the only remaining case, which is $w_{6} = u A # A v t$ . As ${B B B, B $ B, $, A # B, # X ∣ X \in T \cup {B}} \cap s u b (w_{6}) = \emptyset$ , the only applicable rule is Rule 5. Hence, (A) $w_{7} = u $ $ # A v t$ , or (B) $w_{7} = u A # $ $ v t$ , or (C) $w_{7} = u^{'} A # A v^{'} t$ , where $u = u^{'}$ or $v = v^{'}$ and exactly one occurrence of A in $u v$ was replaced by $$ $$ in order to get $u^{'} v^{'}$ . As ${$ $, #} \subseteq s u b (w_{7})$ , only Rules 3, 6, or $8. X$ might be applicable. In Case (A), only Rule 6 is applicable by checking the permitting conditions, i.e., $w_{8} = u $ $ A v t$ . In Case (B), Rule 3 is not applicable, as the symbol to the right of $# $$ is not A or B. The permitting conditions of Rules 6 and $8. X$ require the substring $$ #$ , which is not present in this case. The same reasoning shows that Case (C) knows no continuation. To summarize, we are forced to $w_{8} = u $ $ A v t$ . As $ is present in $w_{8}$ , we cannot apply Rules 1, 4, 5, or $9. X$ . As ${B $ B, # $ A, # $ B, #} \cap s u b (w_{8}) = \emptyset$ , the only applicable rule is Rule 7. This leads us to $w_{9} = u $ $ # v t$ or $u^{'} $ $ A v^{'} t$ , where $u^{'} = u$ or $v^{'} = v$ , and either $v^{'}$ is obtained from v by replacing one occurrence of A by #, or $u^{'}$ is derived from u in a similar fashion. Anyways, the presence of $ and # in the new string restricts us to using Rules 3, 6, $8. X$ in the next derivation step, which always requires $ and # to be neighboring symbols, leaving us with $w_{9} = u $ $ # v t$ as the only possibility, as u cannot end with A (and hence $u^{'}$ cannot end with #) and v cannot start with A (and hence $v^{'}$ cannot start with #).

As ${$ $, #} \subseteq s u b (w_{9})$ , only Rules 3, 6 or $8. X$ might be applicable to $w_{9}$ . The permitting condition of Rule 3 is not satisfied. If we apply Rule 6, we arrive at $u $ $ v t$ . As can be checked by a case-by-case analysis, there is no rule that applies to transform $u $ $ v t$ any further in $G^{'}$ . If we use Rule $8. X$ instead, we get $w_{10} = u $ # v t$ . Again, only Rules 3, 6 or $8. X$ might be applicable. The required permitting strings of Rules 3 and 6 are not subwords of $w_{10}$ . Hence, we have to apply Rule $8. X$ once more, leading to $w_{11} = u # v t$ . Now, recall that u ends with a B and v starts with a B, unless they are empty. Hence, Rules 4 and 5 do not apply. The presence of # prevents applying Rules 2 and 7. The absence of $ does not allow us to apply Rules 3, 6, 7 or $8. X$ , either. As $B B B \notin s u b (w_{11})$ , Rule 1 cannot be applied. Hence, only Rule $9. X$ is applicable, yielding $w_{12} = u v t$ . As $w \Rightarrow w_{12}$ in G is valid (recall that we are still considering Case (i) from the beginning of this analysis), the induction step is shown.

There is one issue that needs to be finally addressed. As S is introduced as an auxiliary symbol in the conditional rules in Fig. 3, within $G^{'}$ , a new simulation of a derivation $S \Rightarrow^{} x$ in G might start. This possibility is stopped by the fact that rules of G that are terminating the first phase, i.e., rules of the form $S \to w$ for $S \notin s u b (w)$ , are now guarded by the condition checking if $ is absent. More precisely, we have to prevent rule $δ S$ from being applicable after an attempted re-start of a simulation of phase one. We can first assume that the only way to generate the empty word within G is by using a rule $S \to λ$ , which would be put into $P_{c f}$ anyways. This means that, starting with S, some string $u S v t$ from ${A B, A B B}^{+} {S} {B A, B B A}^{} T^{}$ might be created. Now, in order to keep Rule $δ S$ from being applicable, $v \in {B A, B B A}^{}$ must be empty. Hence, only rules of the form $S \to u^{'} S$ have been applied, but there is exactly one rule of this form, and this belongs to $P_{c f}$ and is hence guarded by the forbidden condition $ in $G^{'}$ . So, if such a restart is attempted, then this could never lead to a terminal string.
Remark 3.
As the number of rules listed under $8. X$ and $9. X$ in Fig. 3 can grow based on the size of the terminal alphabet, the number of conditional rules can only be bounded by $9 + 2 (| T | + 1) + | P_{c f} |$ , where $P_{c f}$ collects all rules of the simulated grammar G that are used for terminating the second stage of the first phase in a derivation of a Geffert normal form grammar. We also refer to the discussions of Remark 1.

We can get a better bound on the number of conditional rules at the expense of one additional nonterminal $†$ as shown in Fig. 4.

Figure 4.
Semi-conditional rules simulating $ABBBA \to λ$ and $S \to w$ .
Theorem 4.
For each recursively enumerable language L, there is a semi-conditional grammar of degree* $(3, 1)$ with only six nonterminals and 13 conditional rules that describes L.
Proof.
Instead of giving a full proof, we only list the rules simulating the given $(3, 1)$ -GNF grammar in Fig. 4 and make the following remarks.
As S is no longer (ab)used as an auxiliary symbol, there is no need to shield the applications of S any more.

Also, we allow deleting $ and # when no A’s are present instead of testing for terminal symbols to the right of # (see Rules $8^{'}$ and $9^{'}$ ). The reason is that A’s can be absent only at the very end of the simulation of Phase 2 of G. Hence, both tests are equivalent.
The remaining (rather obvious) details are left to the reader. In particular, an intended derivation of the suggested simulating grammar follows closely the one presented in Eq. (1) for the previous simulation.
5. Future research questions

The interested reader might have wondered why we restricted our attention to (simple) semi-conditional grammars of degree $(i, j)$ with $i > 1$ , although even degree $(1, 1)$ is known to suffice for computational completeness. However, the published construction of [16] (simulating matrix grammars, based on [18]) is not helpful to get any bounds on the nonterminal complexity of such systems; even if we start out with a matrix grammar with a few nonterminals (as done in the construction of Mayer), and if we notice that few nonterminals suffice in matrix grammars, as shown in [7] for the currently best bounds, then we still arrive at a semi-conditional grammar with quite a number of nonterminals, as the matrix grammars considered in [18] are binary5 to start with, while in [7], the matrix grammars that are constructed contain arbitrarily many rule in their matrices. The standard construction to show that binary normal form matrix grammars characterize RE introduces an unbounded number of nonterminals. The new construction indicated in Footnote 2 uses a finite number but not few nonterminals. We pose it as an open question to construct a (simple) semi-conditional grammars of degree $(1, 1)$ using only, say, ten nonterminals.

Clearly, other open questions concern the optimality of our nonterminal complexity results for degrees $(2, 1)$ , $(2, 2)$ or $(3, 1)$ . It is also still somewhat unclear how to use longer forbidding conditions in order to lower the number of nonterminals or the number of conditional rules necessary to achieve computational completeness. Recall that our result for degree $(2, 2)$ is the only one ever obtained in this direction. Intuitively speaking, bigger degrees are particularly interesting when dealing with $(3, 1)$ -GNF or similar normal forms. They could help further reduce the number of nonterminals.

If one has another look at Tables 1 and 2, one observes a certain discrepancy. For instance, one observes that with degree $(2, 1)$ , only seven nonterminals and six conditional rules suffice to characterize RE according to the result of Okubo [20], while nine nonterminals and eight conditional rules seem to be necessary (at least, they are sufficient) to characterize RE according to a result of Fernau et al. [9]. The difference is that with simple SCG, in all rules, at least one context string is absent. Conversely, let us call a rule that has both a permitting and a forbidden string attached to it strongly conditional. Hence, we can rephrase [9, Theorem 3.1] as: RE can be characterized by SCG of degree $(2, 1)$ with nine nonterminals and eight conditional rules, none of which are strongly conditional. By way of contrast, Okubo’s result (looking at his proof) gives: RE can be characterized by SCG of degree $(2, 1)$ with seven nonterminals and six conditional rules, four of which are strongly conditional. Hence, in a sense, counting strongly conditional rules (on top) offers another view on simple versus non-simple semi-conditional grammars. We could now ask questions like: Can we find results that characterize RE by semi-conditional grammars of degree $(2, 1)$ that have, say, eight nonterminals but use only two strongly conditional rules? This opens up another research venue. Actually, some results in this research line have been published in a paper presented at CiE 2024 [10].

Finally, let us mention that – on top of trying to achieve computational completeness results with as little resources as possible – one could also strive to understand if few(er) resources are needed to describe non-recursive languages. Here, we refer to Remark 1. In particular, one could try to further lower the nonterminal complexity to achieve this goal compared to the more ambitious target to describe all recursively enumerable languages. To achieve this more modest goal, one could also try to simulate mechanisms that are unknown to describe all of the recursively enumerable languages, although they contain undecidable languages, as exemplified by limited Lindenmayer systems or regulated grammars with unconditional transfer, see [1,3–5].

Footnotes

Acknowledgements

The research leading to this paper was in large parts undertaken when Rufus Oladele and Lakshmanan Kuppusamy visited the University of Trier in September and October, 2017. The final writing of this paper was initiated during another research visit of Lakshmanan Kuppusamy to Trier during September 2022. All authors gratefully acknowledge the possibility to make use of third party overhead money provided by the University of Trier to support the mentioned travels. The first and second authors would like to thank the Indo-German (DST-DAAD) research collaboration project “Succinct Representation of Grammars: Theory and Applications” (No. DST/INT/DAAD/P-01-2024(G), DAAD No. 57724085) as the paper was finished under the scope and objective of the project. We are also grateful to the comments of the reviewers that helped improve our manuscript.

Notes

References

Dassow

, A remark on limited 0L systems, Journal of Information Processing and Cybernetics EIK 24(6) (1988), 287–291.

Dassow

Păun

, Regulated Rewriting in Formal Language Theory, EATCS Monographs in Theoretical Computer Science, Vol. 18, Springer, 1989.

Fernau

, Membership for 1-limited ET0L languages is not decidable, Journal of Information Processing and Cybernetics EIK 30(4) (1994), 191–211.

Fernau

, Membership for k-limited ET0L languages is not decidable, Journal of Automata, Languages and Combinatorics 1 (1996), 243–245.

Fernau

, Unconditional transfer in regulated rewriting, Acta Informatica 34 (1997), 837–857. doi:10.1007/s002360050108.

Fernau

, Parsimonious computational completeness, in: Developments in Language Theory – 25th International Conference, DLT, Moreira

Reis

, eds, LNCS, Vol. 12811, Springer, 2021, pp. 12–26. doi:10.1007/978-3-030-81508-0_2.

Fernau

Freund

Oswald

Reinhardt

, Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars, Journal of Automata, Languages and Combinatorics 12(1/2) (2007), 117–138.

Fernau

Kuppusamy

Oladele

R.O.

, New nonterminal complexity results for semi-conditional grammars, in: Sailing Routes in the World of Computation, 14th Conference on Computability in Europe, CiE, Manea

Miller

R.G.

Nowotka

, eds, LNCS, Vol. 10936, Springer, 2018, pp. 172–182. doi:10.1007/978-3-319-94418-0_18.

Fernau

Kuppusamy

Oladele

R.O.

Raman

, Improved descriptional complexity results for simple semi-conditional grammars, Fundamenta Informaticae 181 (2021), 189–211. doi:10.3233/FI-2021-2056.

10.

Fernau

Kuppusamy

Raman

, Counting simple rules in semi-conditional grammars is not simple, in: Twenty Years of Theoretical and Practical Synergies, 20th Conference on Computability in Europe, CiE, L.L. Patey and E. Pimentel, eds, LNCS, Vol. 14773, Springer, 2024, pp. 192–204. doi:10.1007/978-3-031-64309-5_16.

11.

Geffert

, A representation of recursively enumerable languages by two homomorphisms and a quotient, Theoretical Computer Science 62 (1988), 235–249. doi:10.1016/0304-3975(88)90068-0.

12.

Geffert

, Normal forms for phrase-structure grammars, RAIRO Informatique théorique et Applications/Theoretical Informatics and Applications 25 (1991), 473–498. doi:10.1051/ita/1991250504731.

13.

Gruska

, On a classification of context-free languages, Kybernetika 3(1) (1967), 22–29.

14.

Gruska

, A few remarks on the index of context-free grammars and languages, Information and Control (now Information and Computation) 19 (1971), 216–223. doi:10.1016/S0019-9958(71)90095-7.

15.

Masopust

, Formal Models: Regulation and Reduction, PhD thesis, Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic, 2007.

16.

Masopust

, A note on the generative power of some simple variants of context-free grammars regulated by context conditions, in: Language and Automata Theory and Applications, LATA, Dediu

A.-H.

Ionescu

A.-M.

Martín-Vide

, eds, LNCS, Vol. 5457, Springer, 2009, pp. 554–565. doi:10.1007/978-3-642-00982-2_47.

17.

Masopust

Meduna

, Descriptional complexity of semi-conditional grammars, Information Processing Letters 104(1) (2007), 29–31. doi:10.1016/j.ipl.2007.05.002.

18.

Mayer

, Some restrictive devices for context-free languages, Information and Control (now Information and Computation) 20 (1972), 69–92. doi:10.1016/S0019-9958(72)90287-2.

19.

Meduna

Gopalaratnam

, On semi-conditional grammars with productions having either forbidding or permitting conditions, Acta Cybernetica 11 (1994), 309–323.

20.

Okubo

, A note on the descriptional complexity of semi-conditional grammars, Information Processing Letters 110(1) (2009), 36–40. doi:10.1016/j.ipl.2009.10.002.

21.

Păun

, A variant of random context grammars: Semi-conditional grammars, Theoretical Computer Science 41 (1985), 1–17. doi:10.1016/0304-3975(85)90056-8.

22.

Vaszil

, On the descriptional complexity of some rewriting mechanisms regulated by context conditions, Theoretical Computer Science 330 (2005), 361–373. doi:10.1016/j.tcs.2004.06.032.

On the computational completeness of several descriptional complexity restrictions of semi-conditional grammars

Abstract

Keywords

1. Introduction

Table 1 Survey on nonterminal complexity results for semi-conditional grammars. Degree ( i , j ) # Nonterminals # Conditional Rules Reference (1,1) * * [16] (2,1) 8 7 [17] (2,1) 7 6 [20] (2,1) 6 7 + | P c f | Thm. 1 (2,2) 6 6 Thm. 2 (3,1) 5 9 + 2 ( | T | + 1 ) + | P c f | Thm. 3 (3,1) 6 13 Thm. 4

2.1. Semi-conditional grammars

3. Properties of ( 3 , 1 ) -GNF and ( 4 , 2 ) -GNF

Footnotes

Acknowledgements

Notes

References

3. Properties of $(3, 1)$ -GNF and $(4, 2)$ -GNF