On the degrees of non-regularity and non-context-freeness
- We study the derivational complexity of context-free and context-sensitive grammars by counting the maximal number of non-regular and non-context-free rules used in a derivation, respectively. The degree of non-regularity/non-context-freeness of a language is the minimum degree of non-regularity/non-context-freeness of context-free/context-sensitive grammars generating it. A language has finite degree of non-regularity iff it is regular. We give a condition for deciding whether the degree of non-regularity of a given unambiguous context-free grammar is finite. The problem becomes undecidable for arbitrary linear context-free grammars. The degree of non-regularity of unambiguous context-free grammars generating non-regular languages as well as that of grammars generating deterministic context-free languages that are not regular is of order Omega(n). Context-free non-regular languages of sublinear degree of non-regularity are presented. A language has finite degree of non-context-freeness if it is context-free. Context-sensitiveWe study the derivational complexity of context-free and context-sensitive grammars by counting the maximal number of non-regular and non-context-free rules used in a derivation, respectively. The degree of non-regularity/non-context-freeness of a language is the minimum degree of non-regularity/non-context-freeness of context-free/context-sensitive grammars generating it. A language has finite degree of non-regularity iff it is regular. We give a condition for deciding whether the degree of non-regularity of a given unambiguous context-free grammar is finite. The problem becomes undecidable for arbitrary linear context-free grammars. The degree of non-regularity of unambiguous context-free grammars generating non-regular languages as well as that of grammars generating deterministic context-free languages that are not regular is of order Omega(n). Context-free non-regular languages of sublinear degree of non-regularity are presented. A language has finite degree of non-context-freeness if it is context-free. Context-sensitive grammars with a quadratic degree of non-context-freeness are more powerful than those of a linear degree.…
Verfasserangaben: | Henning BordihnORCiD, Victor MitranaORCiDGND |
---|---|
DOI: | https://doi.org/10.1016/j.jcss.2019.09.003 |
ISSN: | 0022-0000 |
ISSN: | 1090-2724 |
Titel des übergeordneten Werks (Englisch): | Journal of computer and system sciences |
Verlag: | Elsevier |
Verlagsort: | San Diego, Calif. [u.a.] |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 01.03.2020 |
Erscheinungsjahr: | 2020 |
Datum der Freischaltung: | 14.07.2023 |
Freies Schlagwort / Tag: | context-free grammar; context-sensitive; degree of non-context-freeness; degree of non-regularity; grammar |
Band: | 108 |
Seitenanzahl: | 14 |
Erste Seite: | 104 |
Letzte Seite: | 117 |
Fördernde Institution: | Alexander von Humboldt FoundationAlexander von Humboldt Foundation |
Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme |
Peer Review: | Referiert |