TY  - JOUR
A1  - Bordihn, Henning
A1  - Mitrana, Victor
T1  - On the degrees of non-regularity and non-context-freeness
T2  - Journal of computer and system sciences
N2  - 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-sensitive grammars with a quadratic degree of non-context-freeness are more powerful than those of a linear degree.
KW  - context-free grammar
KW  - degree of non-regularity
KW  - context-sensitive
KW  - grammar
KW  - degree of non-context-freeness
Y1  - 2020
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/59961
SN  - 0022-0000
SN  - 1090-2724
VL  - 108
SP  - 104
EP  - 117
PB  - Elsevier
CY  - San Diego, Calif. [u.a.]
ER  -