On the degrees of non-regularity and non-context-freeness

DOI10.1016/J.JCSS.2019.09.003MaRDI QIDQ2009649zbMATH OpenOpenAlexWikidataFDO

Authors Henning Bordihn, Victor Mitrana

Publication date 29 November 2019

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2019.09.003

zbMATH Keywords

context-free grammar context-sensitive grammar degree of non-context-freeness degree of non-regularity

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Review text

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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: On the degrees of non-regularity and non-context-freeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2009649)