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 |
