- search hit 1 of 1
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 |