Header menu link for other important links
X
Improved descriptional complexity results on generalized forbidding grammars
H. Fernau, , R.O. Oladele, I. Raman
Published in Springer Verlag
2019
Volume: 11394 LNCS
   
Pages: 174 - 188
Abstract
In formal language theory, if a grammar consists of rules of the type (r, Fr), where r is a context-free rule and Fr is an associated finite set of strings called the forbidding set, such that r can be applied to a string only if none of the strings in Fr is present in the string, then the grammar is said to be a generalized forbidding (GF) grammar. There are four main parameters that describe the size of a GF grammar, namely, (i) d, the maximum length of strings in the forbidding sets, (ii) i, the maximum cardinality of the forbidding sets, (iii) n, the number of nonterminals used in the grammar, and (iv) c, the number of rules with nonempty forbidding set. The family of languages described by a GF grammar of size (at most) (d, i, n, c) is denoted by GF(d, i, n, c). We study for what sizes of generalized forbidding grammars one can obtain the computational power of Turing machines. We specifically show this result for sizes (2, 6, 8, 6), (2, 5, 8, 8), (2, 4, 9, 9) and (2, 3, 20, 18). These results improve on previous results on the descriptional complexity of generalized forbidding grammars. © Springer Nature Switzerland AG 2019.