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.…
| Author details: | Henning BordihnORCiD, Victor MitranaORCiDGND |
|---|---|
| DOI: | https://doi.org/10.1016/j.jcss.2019.09.003 |
| ISSN: | 0022-0000 |
| ISSN: | 1090-2724 |
| Title of parent work (English): | Journal of computer and system sciences |
| Publisher: | Elsevier |
| Place of publishing: | San Diego, Calif. [u.a.] |
| Publication type: | Article |
| Language: | English |
| Date of first publication: | 2020/03/01 |
| Publication year: | 2020 |
| Release date: | 2023/07/14 |
| Tag: | context-free grammar; context-sensitive; degree of non-context-freeness; degree of non-regularity; grammar |
| Volume: | 108 |
| Number of pages: | 14 |
| First page: | 104 |
| Last Page: | 117 |
| Funding institution: | Alexander von Humboldt FoundationAlexander von Humboldt Foundation |
| Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme |
| Peer review: | Referiert |
