# On the Grammatical Complexity of Finite Languages

Markus Holzer, Simon Wolfsteiner

► To cite this version:

Markus Holzer, Simon Wolfsteiner. On the Grammatical Complexity of Finite Languages. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.151-162, 10.1007/978-3-319-94631-3_13 . hal-01905630

HAL Id: hal-01905630

https://inria.hal.science/hal-01905630

Submitted on 26 Oct 2018

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# On the Grammatical Complexity of Finite Languages

Markus Holzer¹ and Simon Wolfsteiner²*

¹ Institut für Informatik, Universität Giessen,
Arndtstr. 2, 35392 Giessen, Germany
holzer@informatik.uni-giessen.de

² Institut für Diskrete Mathematik und Geometrie, TU Wien,
Wiedner Hauptstr. 8–10, 1040 Wien, Austria
simon.wolfsteiner@tuwien.ac.at

**Abstract.** We study the grammatical production complexity of *finite* languages w.r.t. (i) different interpretations of approximation, i.e., equivalence, cover, and scattered cover, and (ii) whether the underlying grammar generates a finite or infinite language. In case the generated language is infinite, the intersection with all words up to a certain length has to be considered in order to obtain the finite language under consideration. In this way, we obtain six different measures for regular, linear context-free, and context-free grammars. We compare these measures according to the taxonomy introduced in [J. DASSOW, GH. PĂUN: *Regulated Rewriting in Formal Language Theory*, 1989] with each other by fixing the grammar type and varying the complexity measure and the other way around, that is, by fixing the complexity measure and varying the grammar type. In both of these cases, we develop an almost complete picture, which gives new and interesting insights into the old topic of grammatical production complexity.

## 1 Introduction

Measures of descriptional complexity or cost functions have a long and fruitful history. Most approaches to defining descriptional complexity measures are based on quantifying the ability of a device—automaton or grammar—to approximate languages (by finite subsets). The interesting quantities in the case of automata and grammars are, e.g., the number of states or transitions and the number of nonterminals or productions, respectively. For instance, finite languages can be represented by ordinary deterministic finite automata (DFAs) or by cover finite automata (CFAs)—roughly speaking a CFA is a DFA $A$ and a natural number $ℓ$ whose accepted language is defined as $L(A) \cap \Sigma^{\leq ℓ}$. For a precise definition of CFAs, we refer the reader to [6]. This gives rise to two different complexity

<footnote>* This research was completed while the author was on leave at the Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany, in 2017 and is supported by the Vienna Science Fund (WWTF) project VRG12-004.</footnote>
measures: for a finite language $L \subseteq \Sigma^{\le l}$, one defines the DFA state and the CFA state complexity as<fnref n="3" />

$$ \mathbf{DFAc}(L) = \min\{|A| \mid A \text{ is a DFA and } L = L(A)\} \quad (1) $$

and

$$ \mathbf{DFAc}_{\infty}(L) = \min\{|A| \mid A \text{ is a DFA and } L = L(A) \cap \Sigma^{\le l}\}, $$

respectively, where $|A|$ refers to the number of states of the automaton $A$. Obviously, $\mathbf{DFAc}_{\infty}(L) \le \mathbf{DFAc}(L)$, for every finite language $L$. Note that equality is possible for certain finite languages. It is worth mentioning that although these measures look very similar in their definitions, they can differ quite immensely when applied to the same language. For instance, there is a finite language $L$ such that $\mathbf{DFAc}_{\infty}(L) = 1$, but $\mathbf{DFAc}(L) = n$, for every $n \ge 1$. Hence, the gap between both measures can be arbitrarily large. In general, complexity gaps can be classified according to the different growth rates of the complexity measures. To this end, a notion was introduced in [7], which defines three categories $\le^1$, $\le^2$, and $\le^3$ of increasing complexity gaps; a precise definition is given later. The aforementioned complexity gap of arbitrary size between DFAs and CFAs is a gap of highest type, which is simply written as $c_{\infty} \le_{\text{DFA}}^3 c$. This is one example of a complexity measure, but one can find legions of other automata-based descriptional complexity measures in the literature.

In this paper, we study the grammatical production complexity of finite languages. This topic is not new, and already in [3–5], measures similar in definition to (1), for regular (REG), linear context-free (LIN), and context-free grammars (CFG) have been investigated; they are named $Xc$, for $X \in \{\text{REG, LIN, CF}\}$. For instance, there it has been shown that there are incompressible finite languages for each grammar type mentioned above, i.e., languages that need at least as many productions of a certain type as there are words in that language. To the best of our knowledge, a classification of these grammatical measures in the sense of [7] has not been done yet. We close this gap and, moreover, also consider natural variants of $Xc$ by varying the equivalence condition $L = L(A)$ in (1) to $L \subseteq L(A)$ and $L(A)$ finite (cover) or even $L \le L(A)$ and $L(A)$ finite (scattered cover), where $\le$ refers to the scattered subword relation—similarly this can be done for $L = L(A) \cap \Sigma^{\le l}$ in $Xc_{\infty}$, too. This leads to the additional grammatical measures (i) $Xcc$ and $Xcc_{\infty}$ (cover) and (ii) $Xsc$ and $Xsc_{\infty}$ (scattered cover), for $X \in \{\text{REG, LIN, CF}\}$. The variation $Xcc$ is inspired by recent results on proof complexity in first-order logic, a research topic, which, from a first glance, seems completely unrelated to grammatical complexity, that connects the number of certain inference rules used in a specific logical calculus with the number of productions needed to cover a certain finite language [8]. For further results on the cover complexity of finite languages, see also [9]. We compare these measures according to the taxonomy introduced in [7] with each

<footnote n="3">³ Observe that it is common in the literature to refer to the DFA and the CFA state complexity as sc and csc, respectively. We adapted the notation in order to be consistent with the notation used throughout this paper.</footnote>
other by (i) fixing the grammar type and varying the complexity measure and (ii) by fixing the complexity measure and varying the grammar type. In both of these cases, we develop an almost complete picture. As a byproduct, we also show that there are finite languages with large complexity. More precisely, the language of even length palindromes $P_n = \{w$|w$^R | w \in \{a, b\}^{\le n}\}$ requires at least $\Omega(2^n)$ productions to be generated by a regular grammar. Moreover, the triple language $T_n = \{w$|w#w | w \in \{a, b\}^n\}$ can only be generated by grammars of type X, for $X \in \{\text{REG}, \text{LIN}, \text{CF}\}$, by simply listing all words in $T_n$, i.e., $X_c(T_n) = \Omega(2^n)$.

## 2 Preliminaries

We assume that the reader is familiar with the basic notions of formal language theory as contained in [11]. Nevertheless, to fix notation and terminology, we introduce the basic notions and results relevant to this paper in this section.

Let $\Sigma$ be a finite alphabet. Then $\Sigma^*$ denotes the set of all words over the finite alphabet $\Sigma$ including the empty word $\varepsilon$ and we write $\Sigma^+$ for $\Sigma^* \setminus \{\varepsilon\}$. The length of a word $w$ in $\Sigma^*$ is denoted by $|w|$. In particular, the length of the empty word $\varepsilon$ is 0, i.e., $|\varepsilon| = 0$. The reversal of a word is defined as follows: $\varepsilon^R = \varepsilon$ and $(wa)^R = aw^R$, for $w \in \Sigma^*$ and $a \in \Sigma \cup \{\varepsilon\}$. Let $\ell \ge 0$. Then $\Sigma^\ell$ and $\Sigma^{\le \ell}$ refers to the set of all words over $\Sigma$ of length exactly $\ell$ and at most $\ell$, respectively. A subset $L$ of $\Sigma^*$ is called a language. Any language $L \subseteq \Sigma^{\le \ell}$, for $\ell \ge 0$, is called finite and, unless stated otherwise, we always assume $\ell = \max\{|w| \mid w \in L\}$. If $L$ is a subset of $\Sigma^\ell$, for $\ell \ge 0$, then $L$ is called a uniform language. This means that in a uniform language all words have the same length.

A context-free grammar (CFG) is a quadruple $G = (N, \Sigma, P, S)$, where $N$ and $\Sigma$ are disjoint alphabets of nonterminals and terminals, respectively, $S \in N$ is the start symbol, and $P$ is a finite set of productions of the form $A \to \alpha$, where $A \in N$ and $\alpha \in (N \cup \Sigma)^*$. As usual, the derivation relation of $G$ is denoted by $\Rightarrow_G$ and the reflexive and transitive closure of $\Rightarrow_G$ is written as $\Rightarrow_G^*$. The language generated by $G$ is defined as $L(G) = \{w \in \Sigma^* \mid S \Rightarrow_G^* w\}$. We also consider the following restrictions of context-free grammars: (i) a context-free grammar is said to be linear context-free (LIN) if the productions are of the form $A \to \alpha$, where $A \in N$ and $\alpha \in \Sigma^*(N \cup \{\varepsilon\})\Sigma^*$, and (ii) a context-free grammar is said to be right-linear or regular (REG) if the productions are of the form $A \to \alpha$, where $A \in N$ and $\alpha \in \Sigma^*(N \cup \{\varepsilon\})$. Furthermore, $\Gamma$ will denote the set of grammar types in the sequel, that is, $\Gamma = \{\text{REG}, \text{LIN}, \text{CF}\}$.

Let $G = (N, \Sigma, P, S)$ be a context-free grammar. By $|G|$, we denote the number of productions of $G$, i.e., the cardinality of $P$. Then the (exact) X-complexity (or X-complexity for short) of a finite language $L$ w.r.t. X-grammars, for $X \in \Gamma$, is defined as

$$X_c(L) = \min\{|G| \mid G \text{ is an X-grammar with } L = L(G) \text{ and } L(G) \text{ finite}\}.$$

The additional condition that $L(G)$ is finite is redundant, but becomes important whenever we replace $L = L(G)$ by $L \subseteq L(G)$ or some other language-relating
property. Similarly, the infinite X-complexity of a finite language $L \subseteq \Sigma^{\le \ell}$ is defined as

$$Xc_{\infty}(L) = \min\{|G| \mid G \text{ is an X-grammar with } L = L(G) \cap \Sigma^{\le \ell}\}.$$

Note that in the definition of $Xc_{\infty}$, the grammar $G$ is allowed to generate an infinite language. If we replace $L = L(G)$ and $L = L(G) \cap \Sigma^{\le \ell}$ in the definitions of $Xc(L)$ and $Xc_{\infty}(L)$, respectively, by $L \subseteq L(G)$ and $L \subseteq L(G) \cap \Sigma^{\le \ell}$, respectively, then we get the definitions for the X-cover-complexity $Xcc(L)$ and the infinite X-cover-complexity $Xcc_{\infty}(L)$, respectively. The scattered subword relation $\le$ is defined as follows: let $w = w_1u_1w_2u_2\dots u_{n-1}w_n$ be a word with $w_i, u_j \in \Sigma^*$, for $1 \le i \le n$ and $1 \le j \le n-1$. Then the word $w' = w_1w_2\dots w_n$ is called a scattered subword of $w$ and we write $w' \le w$ in this case. We extend the relation $\le$ from words to languages $L_1$ and $L_2$ as follows: $L_1 \le L_2$ if for all words $w_1 \in L_1$, there is a word $w_2 \in L_2$ such that $w_1 \le w_2$. If $L_1 \le L_2$ holds, we say that $L_1$ is a scattered sublanguage of $L_2$. We, obtain the definitions for $Xsc(L)$ and $Xsc_{\infty}(L)$ if we replace $L = L(G)$ and $L = L(G) \cap \Sigma^{\le \ell}$ by $L \le L(G)$ and $L \le L(G) \cap \Sigma^{\le \ell}$, respectively, in the definitions of $Xc(L)$ and $Xc_{\infty}(L)$, respectively. This results in the X-scattered-complexity and the infinite X-scattered-complexity, respectively.

Note that the definitions of $Xc$, $Xcc$, and $Xsc$ also have the additional requirement that $L(G)$ is a finite language. In the following, $\mathcal{M}$ will denote the set of measure types, i.e., $\mathcal{M} = \{c, cc, sc, c_{\infty}, cc_{\infty}, sc_{\infty}\}$. By definition, for $\tau \in \mathcal{M}$, the following relations hold:

$$\mathrm{CFG} \leq_{\tau} \mathrm{LIN} \leq_{\tau} \mathrm{REG}, \qquad (2)$$

where, for $X, Y \in \Gamma$, we define $X \leq_{\tau} Y$ if and only if $X\tau(L) \leq_{\Gamma} Y\tau(L)$, for all finite languages $L$. In case that $X \leq_{\tau} Y$, we say that $X$ is more succinct than $Y$ (w.r.t. the complexity measure $\tau$).

We say that $G$ is a minimal X-grammar, for $X \in \Gamma$, w.r.t. the measure $X\tau$ with $\tau \in \mathcal{M}$, if $|G| = X\tau(L)$. In the case of the measure $Xc$, we speak of a minimal X-grammar generating a finite language.

Finally, we show that grammars that generate non-trivial uniform languages do not contain $\varepsilon$-productions. To this end, we first need the following result on the length of words generated by some nonterminal from a grammar that describes a finite uniform language.

**Lemma 1.** Let $X \in \Gamma$ and $G = (N, \Sigma, P, S)$ be a minimal X-grammar generating a finite and uniform language. Then, for all $A \in N$, all words occurring in the set $\{w \in \Sigma^* \mid A \Rightarrow_G^* w\}$ have the same length.

An easy consequence of the previous lemma is the next theorem.

**Theorem 2.** Let $X \in \Gamma$ and $G = (N, \Sigma, P, S)$ be a minimal X-grammar generating a finite and uniform language satisfying $L(G) \neq \{\varepsilon\}$. Then $G$ is $\varepsilon$-free, i.e., $P$ does not contain any rule of the form $A \to \varepsilon$, for all $A \in N$.
### 3 Some Bounds on the Various X-Complexities

First, we prove some upper bounds for the finite variants of the introduced grammatical measures. We obtain the following results:

**Theorem 3.** Let $L \subseteq \Sigma^{\le \ell}$ be a finite language over the alphabet $\Sigma$. Then, for $X \in \Gamma$ and $Y \in \{\text{REG}, \text{LIN}\}$, we have

1. $X_{\text{c}}(L) \le \ell + 1$ if $|\Sigma| = 1$, and $X_{\text{c}}(L) \le (|\Sigma|^{\ell+1} - 1)/(|\Sigma| - 1)$, otherwise,

2. $\text{CFcc}(L) \le |\Sigma| + 2$ and $\text{Ycc}(L) \le \ell + 1$ if $|\Sigma| = 1$, and $\text{Ycc}(L) \le (|\Sigma| + 1) \cdot \ell$, otherwise, and

3. $X_{\text{sc}}(L) = 1$ if $L$ is non-empty, and $X_{\text{sc}}(L) = 0$, otherwise.

*Proof.* We argue as follows:

1. Every finite language $L$ can be generated by a grammar of type $X \in \Gamma$ by simply listing all words from $L$. Since there are at most $\sum_{i=0}^{\ell} |\Sigma|^{\ell}$ words of length at most $\ell$ in $L$, the upper bounds of $\ell + 1$ and $(|\Sigma|^{\ell+1} - 1)/(|\Sigma| - 1)$ follow for the cases $|\Sigma| = 1$ and $|\Sigma| \ge 2$, respectively.

2. Consider the context-free grammar $G' = (\{A, S'\}, \Sigma, P', S')$, where $P'$ consists of the productions $S' \to A^\ell$ and $A \to a$, for $a \in \Sigma \cup \{\varepsilon\}$. Clearly, we have $L(G') = \Sigma^{\le \ell}$ and $|G'| = |\Sigma| + 2$, i.e., $\text{CFcc}(\Sigma^{\le \ell}) \le |\Sigma| + 2$. By assumption, $L \subseteq \Sigma^{\le \ell}$. Thus, every grammar generating $\Sigma^{\le \ell}$ automatically covers the language $L$. For $|\Sigma| \ge 2$, consider the regular grammar $G = (N, \Sigma, P, S)$, where $N = \{A_1, A_2, \dots, A_\ell\}$ with $S = A_1$ and

$$P = \{ A_i \to a A_{i+1} \mid a \in \Sigma \text{ and } 1 \le i \le \ell - 1 \} \cup \{ A_\ell \to a \mid a \in \Sigma \} \\ \cup \{ A_i \to \varepsilon \mid 1 \le i \le \ell \}.$$

Obviously, $L(G) = \Sigma^{\le \ell}$ and $|G| = (|\Sigma| + 1) \cdot \ell$. In the case that $|\Sigma| = 1$, we simply list all $\ell + 1$ words occurring in $\Sigma^{\le \ell}$.

3. Assume that $\Sigma = \{a_1, a_2, \dots, a_n\}$ and consider the language $\{(a_1 a_2 \dots a_n)^\ell\}$, which is generated by $G = (\{S\}, \Sigma, \{S \to (a_1 a_2 \dots a_n)^\ell\}, S)$, a regular grammar with a single production rule. Clearly, we have $L \subseteq \{(a_1 a_2 \dots a_n)^\ell\}$, for all nonempty languages $L \subseteq \Sigma^{\le \ell}$. Thus, $X_{\text{sc}}(L) \le 1$. Since any grammar with empty production set can only generate the empty language, we also have $X_{\text{sc}}(L) \ge 1$. In case $L = \emptyset$, we obviously have $X_{\text{sc}}(L) = 0$. $\square$

What about lower bounds for these measures? Observe that $X_{\text{sc}}(L) = 1$ is already a lower bound result. In the seminal paper [5] on concise description of finite languages by different types of grammars, certain languages have been identified that require at least a polynomial number of productions. The proofs of these results are based on [5, Lemma 2.1] which states some easy facts about minimal context-free grammars:

**Lemma 4.** Let $G = (N, \Sigma, P, S)$ be a minimal context-free grammar for the finite language $L$. Then, for every nonterminal $A \in N \setminus \{S\}$, there are strings $\alpha_1$ and $\alpha_2$ with $\alpha_1, \alpha_2 \in (N \cup \Sigma)^*$ and $\alpha_1 \ne \alpha_2$ such that $A \to \alpha_1$ and $A \to \alpha_2$ are
in P. Moreover, for every $A \in N \setminus \{S\}$, the set $L_A(G) = \{w \in \Sigma^* | A \Rightarrow_G^* w\}$ contains at least two words and there is no derivation of the form $A \Rightarrow_G^+ \alpha A \beta$ with $\alpha, \beta \in (N \cup \Sigma)^*$. Finally, for every $A \in N \setminus \{S\}$, there are $u_1, u_2, v_1, v_2 \in \Sigma^*$ such that $u_1 Au_2 \neq v_1 Av_2$ as well as $S \Rightarrow_G^* u_1 Au_2$ and $S \Rightarrow_G^* v_1 Av_2$.

Our first candidate with a large $X$-complexity is the language of all even palindromes (with middle marker) $P_n = \{w \$ w^R | w \in \{a, b\}^{\le n}\}$. We show that any regular grammar generating this language needs at least an exponential number of productions.

**Theorem 5.** Let $n \ge 1$. Then $REG_c(P_n) \ge 2^n$.

*Proof.* In the proof, we will use the following result from [5, Lemma 2.2]: let $G = (N, \Sigma, P, S)$ be a context-free grammar generating a finite language. Then there is a context-free grammar $G_{max} = (N_{max}, \Sigma, P_{max}, S)$ such that $N_{max} \subseteq N$, $P_{max} \subseteq P$, and $L(G_{max}) = L_{max}$, where $L_{max}$ is the subset of $L(G)$ consisting of the words of maximal length. In light of this result, it suffices to show that $REG_c(P'_n) \ge 2^n$, for the language $P'_n = \{w \$ w^R | w \in \{a, b\}^n\}$. To this end, assume that $\Sigma = \{a, b, \$\}$ and $G = (N, \Sigma, P, S)$ is a minimal regular grammar generating $P'_n$ that contains a nonterminal $A \in N \setminus \{S\}$. By Lemma 4, there are derivations $S \Rightarrow_G^* u_1 A$ and $S \Rightarrow_G^* u_2 A$ with $u_1, u_2 \in \Sigma^*$ and $u_1 \neq u_2$ as well as $v_1, v_2 \in \Sigma^*$ with $A \Rightarrow_G^* v_1, A \Rightarrow_G^* v_2$, and $v_1 \neq v_2$. Note that we must have both $|u_1| = |u_2|$ and $|v_1| = |v_2|$, for otherwise we would be able to derive words $w_1$ and $w_2$ with $|w_1| \neq |w_2|$, but $P'_n$ only contains words of the same length. Since $v_1 \neq v_2$ and $|v_1| = |v_2|$, it follows that both $v_1 \neq \varepsilon$ and $v_2 \neq \varepsilon$. Let $w \in \{a, b\}^n$ be arbitrary. We distinguish the following cases:

1. Suppose $u_1 \in \{w\}\{a, b\}^*$. Then we must have $u_1 = w_1 w_2 \$ w_2^R$, where $w = w_1 w_2$ and both $v_1 \in \{a, b\}^*$ and $v_2 \in \{a, b\}^*$ holds. Assume, w.l.o.g., that $v_1 = w_1^R$. Since $v_1 \neq v_2$, it follows that $v_2^R \neq w_1$. Thus, $u_1 v_2 \notin P'_n$. Contradiction.
2. Suppose $u_1 \in \{a, b\}^*$. Then we must have $v_1, v_2 \in \{a, b\}^* \{\$w^R\}$. Assume $w = u_1 w_2$, for some $w_2 \in \{a, b\}^*$ and, w.l.o.g., $v_1 = w_2 \$ w_2^R u_1^R$. Since $v_1 \neq v_2$, it follows that $v_2 = w_2' \$ w_2^R u_1^R$ with $w_2' \neq w_2$. Thus, $u_1 v_2 \notin P'_n$. Contradiction.
Consequently, we have $N = \{S\}$ and so the only way to generate the language $P'_n$ minimally with a regular grammar is to list all of its words using $S$. $\square$

For linear context-free and context-free grammars, one observes that both measures $LIN_c(P_n)$ and $CF_c(P_n)$ are at most linear, as witnessed by the linear context-free grammar $G = (N, \Sigma, P, S)$ with $N = \{S_0, S_1, \dots, S_n\}$, $\Sigma = \{a, b, \$\}$, start symbol $S = S_0$, and the productions

$$ P = \{ S_i \to a S_{i+1} a, S_i \to b S_{i+1} b, S_i \to S_{i+1} \mid 0 \le i \le n-1 \} \cup \{ S_n \to \$ \}, $$
satisfying $L(G) = P_n$, for $n \ge 1$.

Using similar arguments as in the proof of Theorem 5, one can show that the triple language $T_n = \{w \$ w \# w | w \in \{a, b\}^n\}$ has large $X$-complexity, for all grammar types $X$ with $X \in \Gamma$. A detailed proof of this fact can be found in [10].

**Theorem 6.** Let $X \in \Gamma$ and $n \ge 1$. Then $Xc(T_n) = 2^n$.
# 4 Relating Finite and Infinite Complexity Measures

In this section, we will consider several different complexity measures on finite languages and relate them according to a group of relations that vary in strength. By the very nature of these relations, one can distinguish two main categories: the first category fixes the measure type $\tau \in \mathcal{M}$ and then compares the different grammar types in $\Gamma$ with each other w.r.t. the measure type $\tau$—see, e.g., (2). The second category swaps the roles of measure and grammar type, i.e., some grammar type $X \in \Gamma$ is fixed and then the different measure types in $\mathcal{M}$ are compared with each other w.r.t. the grammar type $X$.

## 4.1 Relating Grammar Types

Now, we define several different relations on the grammar types in $\Gamma$ w.r.t. some fixed measure type from $\mathcal{M}$. In this way, we classify the difference between different grammar types w.r.t. the same measure type. This is similar to the notion introduced in [7] for the nonterminal complexity and thus leads to a certain kind of production complexity hierarchy.

Let $X, Y \in \Gamma$ and $\tau \in \mathcal{M}$. Then we write

- $X \leq_{\tau} Y$ if and only if $X\tau(L) \leq Y\tau(L)$, for all finite languages $L$;

- $X \leq_{\tau}^{1} Y$ if and only if there is a constant $c$ such that $X\tau(L) \leq Y\tau(L) + c$, for all finite languages $L$, and there is a sequence of finite languages $(L_i)_{i \geq 0}$ such that $Y\tau(L_i) - X\tau(L_i) \geq i$;

- $X \leq_{\tau}^{2} Y$ if and only if there is a constant $c$ such that $X\tau(L) \leq Y\tau(L) + c$, for all finite languages $L$, and there is a sequence of finite languages $(L_i)_{i \geq 0}$ such that

$$ \lim_{i \to \infty} \frac{X\tau(L_i)}{Y\tau(L_i)} = 0; $$

- $X \leq_{\tau}^{3} Y$ if and only if there is a constant $c$ such that $X\tau(L) \leq Y\tau(L) + c$, for all finite languages $L$, and there is no function $f: \mathbb{N} \to \mathbb{N}$ such that $Y\tau(L) \leq f(X\tau(L))$, for all finite languages $L$.

Clearly, $X \leq_{\tau}^{3} Y$ implies $X \leq_{\tau}^{2} Y$, which, in turn, implies $X \leq_{\tau}^{1} Y$. Moreover, $X \leq_{\tau}^{3} Y$ holds if the first condition of its definition is satisfied and there is a sequence $(L_i)_{i \geq 0}$ of finite languages such that $X\tau(L_i) \leq k$, for some constant $k$ and $Y\tau(L_i) \geq i$. We write $X =_{\tau} Y$ if both $X \leq_{\tau} Y$ and $Y \leq_{\tau} X$ hold.

Now, we are going to relate the different grammar types in $\Gamma$ w.r.t. the finite complexity measure types under investigation. As already mentioned earlier, the relation $CF \leq_{\tau} LIN \leq_{\tau} REG$ holds by definition, for all $\tau \in \mathcal{M}$. The following result was shown in [5]:

**Theorem 7.** It holds that $CF \leq_{c}^{2} LIN \leq_{c}^{2} REG$.

Next, we show that we can only obtain $CF \leq_{\tau}^{3} LIN$ and $CF \leq_{\tau}^{3} REG$, for $\tau \in \{c, cc\}$. As a prerequisite, we need the following result from [5].
**Lemma 8.** Let $G$ be a linear grammar generating a finite language with $|G| \ge 1$. Then $|L(G)| \le 2^{|G|-1}$ and $|G| \ge \log|L(G)| + 1$.

Now, we are ready for the following theorem.

**Theorem 9.** Let $\tau \in \{c, cc\}$. Then

1. $CF \leq_{\tau}^{3} X$, for $X \in \{REG, LIN\}$, and

2. $LIN \leq_{\tau}^{3} REG$ and $REG \leq_{\tau}^{3} LIN$.

*Proof.* 1. Let $L_n = \{a, b\}^{\le n}$, for $n \ge 0$. It was shown in [5], that $CFc(L_n) \le 4$ and $LINc(L_n) \ge n+1$. From Lemma 8, it follows that also $LINcc(L_n) \ge n+1$. Moreover, it holds that $CFcc(L_n) \le CFc(L_n) \le 4$. Consequently, $CF \leq_{\tau}^{3} LIN$. Since $REG\tau(L_n) \ge LIN\tau(L_n) \ge n+1$, we immediately get $CF \leq_{\tau}^{3} REG$.

2. Let $L$ be an arbitrary finite language and $G$ be a minimal linear grammar with $L(G) = L$. Clearly, $REG\tau(L) \le |L| = |L(G)|$. From Lemma 8, it follows that $|L(G)| \le 2^{\text{LIN}\tau(L)-1}$. Thus, $REG\tau(L) \le |L(G)| \le 2^{\text{LIN}\tau(L)-1}$. The function $f: \mathbb{N} \to \mathbb{N}$ with $x \mapsto 2^{x-1}$ fulfills $REG\tau(L') \le f(L\tau(L'))$, for all finite languages $L'$, i.e., $LIN \leq_{\tau}^{3} REG$. Since $L\tau(L') \le REG\tau(L')$, setting $f = id_{\mathbb{N}}$ yields $REG \leq_{\tau}^{3} LIN$. $\square$

For the $X$-scattered-complexity, we have the following situation:

**Theorem 10.** Let $X, Y \in \Gamma$. Then $REG_{=sc} LIN_{=sc} CFG$, but $X \not\leq_{sc}^{i} Y$, for $i \in \{1, 2, 3\}$.

It remains to relate the different grammar types in $\Gamma$ w.r.t. the infinite complexity measure types $c_{\infty}, cc_{\infty}, sc_{\infty}$. For the infinite $X$-complexity we have:

**Theorem 11.** Let $n \ge 1$. Then $REG_{c_{\infty}}(P_n) = \Omega(2^n)$.

*Proof.* The idea of the proof is as follows: let $G = (N, \Sigma, P, S)$ be a regular grammar that is a witness for $REG_{c_{\infty}}(P_n)$. Then we construct a regular grammar generating the finite set $L(G) \cap \Sigma^{\le 2n+1}$. Since this language is equal to $P_n$, we can apply Theorem 5 in order to obtain a lower bound on $|G|$. Although $G$ may contain $\varepsilon$-productions, we can safely assume that $G$ does not contain productions with a right hand-side longer than $2n+2$, since none of these productions generates a word of length less than or equal to $2n+1$ even with erasing rules.

To keep the presentation simple, assume for a moment that the grammar $G$ is in 2-normal form.<fnref n="4" /> Then we apply the triple construction—see, e.g., [11]—to the grammar $G$ and the nondeterministic finite automaton $A = (Q, \Sigma, \delta, q_0, F)$ with $Q = \{0, 1, \dots, 2n+1\}$, initial state $q_0 = 0$, final state set $F = \{2n+1\}$, and the transition function $\delta(i, a) = \{i+1, 2n+1\}$, for $0 \le i < 2n+1$ and $a \in \Sigma$. Then the regular grammar $G' = (N', \Sigma, P', S')$ with $N' = Q \times N \times Q$, start symbol $S' = [0, S, 2n+1]$, and the productions

$$ P' = \{ [i, A, j] \to a \mid \begin{aligned}[t] & A \to a \in P, a \in \Sigma \cup \{\varepsilon\}, \text{ and } j \in \delta(i, a) \\ & \cup \{ [i, A, k] \to a[j, B, k] \mid A \to aB \in P, a \in \Sigma \cup \{\varepsilon\}, \text{ and } j \in \delta(i, a) \} \end{aligned} \} $$

<footnote n="4">⁴ A regular grammar $G = (N, \Sigma, P, S)$ is in 2-normal form if all productions in $P$ are of the form $A \to a$ and $A \to aB$, where $A, B \in N$ and $a \in \Sigma \cup \{\varepsilon\}$.</footnote>
generates the finite language $L(G) \cap \Sigma^{\le 2n+1}$. Observe that $|G'| \le |G| \cdot (2n+2)^3$, because the productions of the form $A \to aB$ from $P$ increase $|G'|$ the most.

Now, we are ready to prove the stated claim. Assume to the contrary that we have $|G| = \text{REG}_{c_\infty}(P_n) = o(2^n)$, for a regular grammar $G$. Then we transform $G$ into an equivalent regular grammar in 2-normal form and apply the above described intersection construction. Let $G'$ refer to the result of these construction steps. The transformation into 2-normal form is done by simply splitting the right hand-side of each production into a sequence of productions of the appropriate form. This increases $|G|$ by at most a factor of $2n+2$. Together with the increase of productions by the triple construction by a factor of at most $(2n+2)^3$, we conclude that $|G'| = o(2^n)$, because $o(2^n \cdot (2n+2)^4) = o(2^n)$. Since the regular grammar $G'$ with $|G'| = o(2^n)$ generates $P_n$, we get a contradiction to Theorem 5. Thus, we obtain $\text{REG}_{c_\infty}(P_n) = \Omega(2^n)$. $\square$

The taxonomy of the next theorem applies to the infinite exact $X$-complexity.

**Theorem 12.** It holds that $\text{CF} \le_{c_\infty}^i \text{REG}$ and $\text{LIN} \le_{c_\infty}^i \text{REG}$, for all $i \in \{1, 2, 3\}$.

Finally, both the infinite $X$-cover and the infinite $X$-scattered-complexity do not classify according to the used taxonomy.

**Theorem 13.** Let $X, Y \in \Gamma$ and $\tau \in \{cc_\infty, sc_\infty\}$. Then we have $X \not\le_{\tau}^{i} Y$, for all $i \in \{1, 2, 3\}$.

We have to leave open the question whether $\text{LIN} \le_{cc}^i \text{REG}$ and $\text{CF} \le_{c_\infty}^j \text{LIN}$, for $i \in \{1, 2\}$ and $j \in \{1, 2, 3\}$, holds.

## 4.2 Relating Complexity Measure Types

Now, we introduce relations for measuring the difference between different measure types w.r.t. some fixed grammar type that we consider in this paper. Therefore, for $\tau, \sigma \in \mathcal{M}$ and $X \in \Gamma$, we similarly define the relations $\tau \le_X \sigma$, $\tau \le_X^{1} \sigma$, $\tau \le_X^{2} \sigma$, and $\tau \le_X^{3} \sigma$ as in the beginning of the previous subsection. For instance, $\tau \le_X^{1} \sigma$ if and only if there is a constant $c$ such that $X\tau(L) \le X\sigma(L) + c$, for all finite languages $L$, and there is a sequence of finite languages $(L_i)_{i \ge 0}$ such that $X\sigma(L_i) - X\tau(L_i) \ge i$.

Clearly, the following chain of implications holds: $\tau \le_X^3 \sigma$ implies $\tau \le_X^2 \sigma$, which, in turn, implies $\tau \le_X^1 \sigma$. Moreover, $\tau \le_X^3 \sigma$ holds if the first condition of its definition is satisfied and there is a sequence $(L_i)_{i \ge 0}$ of finite languages such that $X\tau(L_i) \le c$, for some constant $c$, and $X\sigma(L_i) \ge i$.

We start with comparing the finite $X$- with the infinite $X$-measures. Except for the $X$-scattered-complexity, the infinite versions are more succinct than their finite counterparts.

**Lemma 14.** Let $X \in \Gamma$. Then (i) $c_\infty \le_X c$ and (ii) $cc_\infty \le cc$, but we have (iii) $sc \le_X sc_\infty$.
*Proof.* The first relation follows by definition. Let $L \subseteq \Sigma^{\le l}$. Assume that $G$ is a witness for $Xc(L)$, i.e., $G$ generates a finite language, $L = L(G)$, and $Xc(L) = |G|$. But then also $L = L(G) \cap \Sigma^{\le l}$, which implies $Xc_{\infty}(L) \le Xc(L)$. A similar argumentation applies to the second relation. For the third relation, we argue as follows: in Theorem 3, it was shown that $Xsc(L) = 1$ if $L$ is non-empty and $Xsc(L) = 0$ if $L = \emptyset$. In the latter case, we also have $Xsc_{\infty}(L) = 0$. Thus, we conclude that $Xsc_{\infty}(L) \le Xsc(L)$, for every finite language $L$. $\square$

It is worth mentioning that in the previous lemma, the argumentation used in the proof of the first two relations does not apply to the third one. This is seen as follows: consider the uniform finite language $L = \{a, b\}$. Then the regular grammar $G = (\{S\}, \{a, b\}, \{S \to ab\}, S)$ witnesses $Xsc(L) = 1$, because $L$ is a scattered sublanguage of $\{a, b\}$, i.e., $L \le \{ab\} = L(G)$. But $L(G) \cap \{a, b\}^{\le 1} = \emptyset$. Thus, $|G|$ cannot be used as an upper bound for $Xsc_{\infty}(L)$ and hence $sc_{\infty} \le_X sc$ does not hold in general. Thus, we conclude:

**Corollary 15.** Let $X \in \Gamma$. Then $sc_{\infty} \not\le_X sc$.

Next, we compare the remaining $X$-complexities. Observe that $L_1 = L_2$ implies $L_1 \subseteq L_2$, which, in turn, implies $L_1 \le L_2$. As an easy consequence, we deduce that the (infinite) $X$-scattered-complexity is more succinct than the (infinite) $X$-cover-complexity and it is also easy to see that the (infinite) $X$-cover-complexity is more succinct than the (infinite) $X$-complexity. We summarize:

**Lemma 16.** Let $X \in \Gamma$. Then (i) $sc \le_X cc \le_X c$ and (ii) $sc_{\infty} \le_X cc_{\infty} \le_X c_{\infty}$.

The obtained $\le$-relations are visualized in Figure 1. For the measures $cc$

$$ \begin{array}{ccc} Xcc(\cdot) & \le & Xc(\cdot) \\ \bigvee_I & & \bigvee_I \\ Xsc_{\infty}(\cdot) & \le & Xcc_{\infty}(\cdot) & \le & Xc_{\infty}(\cdot) \\ \bigvee_I & & & & \\ Xsc(\cdot) = 1 & & & & \end{array} $$

**Fig. 1.** Relations between the different grammatical complexity measures on finite languages. In this figure, a $\le$-relation is of type $(i, j, k)$, for $i, j, k \in \{1, 2, 3\}$, if (i) $\le_{\text{CFG}}^i$, (ii) $\le_{\text{LIN}}^j$, and (iii) $\le_{\text{REG}}^k$ hold for the appropriate $X$-measures. All $\le$-relations are of type $(3, 3, 3)$, except $Xcc \le Xc$, $Xcc_{\infty} \le Xcc$, $Xsc \le Xsc_{\infty}$, and $Xsc_{\infty} \le Xcc_{\infty}$, which are of types $(3, 2, 2)$, $(-, 3, 3)$, $(-, -, -)$, and $(-, -, -)$, respectively; the $-$ sign means that it cannot be classified by the taxonomy.

and $c_{\infty}$ we show incomparability w.r.t. the $\le$-relation. Before we can prove
this, we need two prerequisites. The first one is a lower bound on $T_n$ w.r.t. the
infinite X-complexity, which reads as follows—the proof is similar to the proof of
Theorem 11 with the slight modification that we use 2-Greibach normal form<fnref n="5" />
instead of 2-normal form, since we cannot apply the reasoning regarding the
absence of $\varepsilon$-productions to context-free grammars in case of the $c_\infty$-measure.
The change to 2-Greibach normal form induces the fourth root in the lower
bound:

**Theorem 17.** Let $X \in \Gamma$. Then $Xc_\infty(T_n) = \Omega(2^{n/4})$.

The second prerequisite is an exact complexity bound for the language $\Sigma^{\le \ell}$ w.r.t. the finite X-cover-complexity.

**Lemma 18.** Let $X \in \Gamma$ and $\ell \ge 2$. Then $CFcc(\Sigma^{\le \ell}) = |\Sigma| + 2$.

Now, we are ready for the incomparability results:

**Theorem 19.** Let $X \in \Gamma$. Then (i) $cc \not\le_X c_\infty$ and (ii) $c_\infty \not\le_X cc$.

*Proof.* For the proof of (i), observe that the grammar $G = (N, \Sigma, P, S)$ with the productions $P = \{S \to aS, S \to bS, S \to \varepsilon\}$ shows that $Xc_\infty(\{a, b\}^{\le n}) \le 3$. By Lemma 8, we have $n + 1 \le Ycc(\{a, b\}^{\le n})$, for $n \ge 3$ and $Y \in \{\text{REG, LIN}\}$. As a consequence, $Yc_\infty(\{a, b\}^{\le n}) < Ycc(\{a, b\}^{\le n})$. From Lemma 18, it follows that $CFcc(\{a, b\}^{\le n}) \ge 4$, i.e., $CFc_\infty(\{a, b\}^{\le n}) < CFcc(\{a, b\}^{\le n})$. Next, we prove (ii). By Theorem 17, $Xc_\infty(T_n) = \Omega(2^{n/4})$ and, by Theorem 3, we have $Xcc(T_n) \le 15n + 10$. Thus, $Xcc(T_n) < Xc_\infty(T_n)$, for large enough $n$. $\square$

In the remainder of this subsection, we classify the relations between the
X-measures under consideration according to the taxonomy from [7].

**Theorem 20.** Let $X \in \Gamma$ and $Y \in \{\text{REG, LIN}\}$. Then

1. $cc \le_{\text{CFG}}^3 c$ and $cc \le_{Y}^2 c$, but $\tau \not\le_{Y}^3 \sigma$, for all $\tau, \sigma \in \{c, cc\}$ with $\tau \neq \sigma$,

2. $sc \le_X^3 c$,

3. $sc \le_Y^3 cc$, but $\tau \not\le_{\text{CFG}}^i \sigma$, for all $\tau, \sigma \in \{sc, cc\}$ with $\tau \neq \sigma$ and all $i \in \{1, 2, 3\}$,

4. $c_\infty \le_X^3 c$,

5. $\tau \le_X^3 c$, for all $\tau \in \{cc_\infty, sc_\infty\}$,

6. $cc_\infty \le_Y^3 cc$, but $\tau \not\le_{\text{CFG}}^i \sigma$, for $\tau, \sigma \in \{cc, cc_\infty\}$ with $\tau \neq \sigma$ and $i \in \{1, 2, 3\}$,

7. $cc \le_{\text{CFG}}^3 c_\infty$, and

8. $\tau \le_X^3 c_\infty$, for all $\tau \in \{sc, sc_\infty, cc_\infty\}$.

*Proof.* We only prove the first statement. The remaining results can be shown with similar arguments. Let $L_n = \{a^j b^j c^j \mid 1 \le j \le n\}$. In [3], it was shown that $CFc(L_n) = n$. On the other hand, by Theorem 3, we have $CFcc(L_n) \le 5$.

<footnote n="5">⁵ A context-free grammar $G = (N, \Sigma, P, S)$ is in 2-Greibach normal form if all productions in $P$ are of the form $A \to a$, $A \to aB$, $A \to aBC$, or $S \to \varepsilon$, where $A \in N$, $a \in \Sigma$, and $B, C \in N \setminus \{S\}$. The transformation increases the number of productions by at most a polynomial of fourth degree [2].</footnote>
Let $Y \in \{\text{REG}, \text{LIN}\}$ and $T_n = \{w\$w\#w \mid w \in \{a, b\}^n\}$. By Theorem 6, we have $\text{Yc}(T_n) = 2^n$. On the other hand, we have $\text{Ycc}(T_n) \le 15n+10$ by Theorem 3. Hence, $\text{cc} \le_Y^2$. c. Finally, let $L$ be an arbitrary finite language and $f: \mathbb{N} \to \mathbb{N}$ a function defined by $x \mapsto 2^{x-1}$. Moreover, let $G$ be a minimal $Y$-grammar with $L(G) \supset L$. By Lemma 8, we know that $|L| \le |L(G)| \le 2^{\text{Ycc}(L)-1}$. It holds that $\text{Yc}(L) \le |L|$. Thus,

$$ \text{Yc}(L) \leq |L| \leq |L(G)| \leq 2^{\text{Ycc}(L)-1} = f(\text{Ycc}(L)). $$

Hence, $\text{cc} \le_Y^3$. c. If we set $f = \text{id}_N$, it follows that $c \le_Y^3$. cc. $\square$

Finally, we list some incomparability results.

**Theorem 21.** Let $X \in \Gamma$ and $Y \in \{\text{REG}, \text{LIN}\}$. Then, for $i \in \{1, 2, 3\}$, we have

1. $\tau \le_X^i \sigma$, for every $\tau, \sigma \in \{\text{cc}_\infty, \text{sc}_\infty\}$ with $\tau \neq \sigma$,

2. $\tau \le_X^i \sigma$, for every $\tau, \sigma \in \{\text{cc}, \text{sc}_\infty\}$ with $\tau \neq \sigma$,

3. $\tau \le_X^i \sigma$, for every $\tau, \sigma \in \{\text{sc}, \text{sc}_\infty\}$ with $\tau \neq \sigma$,

4. $\tau \le_X^i \sigma$, for every $\tau, \sigma \in \{\text{sc}, \text{cc}_\infty\}$ with $\tau \neq \sigma$, and

5. $\tau \le_Y^i \sigma$, for every $\tau, \sigma \in \{\text{cc}, \text{c}_\infty\}$ with $\tau \neq \sigma$.

*Proof.* We only prove the first statement. The remaining results can be shown with similar arguments. First note that $L \subseteq \Sigma^* \cap \Sigma^\le$ as well as $L \le \Sigma^* \cap \Sigma^\le$, for all finite languages $L$ over $\Sigma$ with $\ell = \max\{|w| \mid w \in L\}$. The universal language $\Sigma^*$, for $\Sigma = \{a_1, a_2, \dots, a_n\}$, can be produced with the following regular productions: $S \to a_1S \mid a_2S \mid \dots \mid a_nS \mid \varepsilon$. Thus, $X\text{cc}_\infty(L) \le |\Sigma| + 1$ and $X\text{sc}_\infty(L) \le |\Sigma| + 1$, for all finite languages $L$ over $\Sigma$. This, however, means that $\tau \le_X^i \sigma$ does not hold for $\tau, \sigma \in \{\text{cc}_\infty, \text{sc}_\infty\}$ and all $i \in \{1, 2, 3\}$. $\square$

## References

1. B. Alspach, P. Eades, and G. Rose. A Lower-bound for the Number of Productions Required for a Certain Class of Languages. *Discrete Appl. Math.*, 6:109–115, 1983.

2. N. Blum and R. Koch. Greibach Normal Form Transformation Revisited. *Inform. Comput.*, 150(1):112–118, 1999.

3. W. Bucher. A Note on a Problem in the Theory of Grammatical Complexity. *Theoret. Comput. Sci.*, 14(3):337–344, 1981.

4. W. Bucher, H. A. Maurer, and K. Culik II. Context-free Complexity of Finite Languages. *Theoret. Comput. Sci.*, 28(3):277–285, 1983.

5. W. Bucher, H. A. Maurer, K. Culik II, and D. Wotschke. Concise Description of Finite Languages. *Theoret. Comput. Sci.*, 14(3):227–246, 1981.

6. C. Câmpeanu, N. Sântean, and S. Yu. Minimal cover-automata for finite languages. *Theoret. Comput. Sci.*, 267(1–2):3–16, 2001.

7. J. Dassow and Gh. Păun. *Regulated Rewriting in Formal Language Theory*, volume 18 of *EATCS Monographs in Theoretical Computer Science*. Springer, 1989.

8. S. Eberhard and S. Hetzl. On the compressibility of finite languages and formal proofs. *Inform. Comput.*, 259(2):191–213, 2018.

9. S. Hetzl and S. Wolfsteiner. Cover Complexity of Finite Languages. In *Proc. 20th DCFS*, LNCS, Halifax, Nova Scotia, Canada, 2018. Springer. To appear.

10. H. Gruber, M. Holzer, and S. Wolfsteiner. On Minimal Grammar Problems for Finite Languages. 2018. Submitted for publication.

11. D. Wood. *Theory of Computation*. John Wiley & Sons, 1987.