On the degrees of non-regularity and non-context-freeness (Q2009649)

The contribution investigates the degree of non-regularity of context-free languages as well as the degree of non-context-freeness of context-sensitive languages. These degrees are measured asymptotically like a complexity function. For a single derivation \(D\) of a word \(w\) in a given context-sensitive grammar \(G\), the degree of non-regularity (respectively, non-context-freeness) is the number of non-regular (respectively, non-context-free) productions used in the derivation \(D\). The degree of a word \(w\) in \(G\) is the minimum of the degrees for all successful derivations of \(w\) in \(G\) (or \(0\) if no successful derivations exist for \(w\)). For a given length \(n\) the degree for words of length \(n\) in \(G\) is the maximum of the degrees for all words of length \(n\). The degree of non-regularity (respectively, non-context-freeness) of a language \(L\) is bounded by a mapping \(f \colon \mathbb N \to \mathbb N\) if there exists a context-free (respectively, context-sensitive) grammar \(G\) that generates \(L\) (i.e. \(L(G) = L\)) and its degree is eventually bounded by \(f\) (i.e. \(G\)'s degree belongs to \(\mathcal O(f)\)). The authors show that a language has finite degree of non-regularity if and only if it is regular. Moreover, it is demonstrated that it is decidable for unambiguous context-free grammars whether they have finite degree of non-regularity. It is well known that checking regularity of a given context-free grammar is undecidable and this remains true even for linear context-free grammars. For non-regular context-free languages, that are generated by context-free grammars that are deterministic or unambiguous, it is demonstrated that their degree is maximal (which is linear). However, context-free languages with non-constant, sublinear (for square root and logarithm) degree of non-regularity are presented. Similarly, a language has finite degree of non-context-freeness if and only if it is context-free. Additional examples illustrate that context-sensitive grammars with quadratic degree of non-context-freeness are more expressive than context-sensitive grammars with linear degree of non-context-freeness. Overall, the paper is well written and can be appreciated by anyone with some background in formal language theory. Some minimal exposure to complexity theory helps to understand the asymptotic notions, but it is not required. The presented examples are quite involved and might require studying additional literature to fully understand the arguments, but the authors present nice high-level descriptions.