Complexity of normal form grammars (Q799380)

This paper considers various descriptive complexity measures for context free languages such as the number of productions, the number of nonterminals, or the total length of the corresponding context free grammar. It is investigated, how those complexities increase when going from \(\epsilon\) -free chain-free reduced grammars to certain normal forms, such as weak Greibach normal form or position restricted grammars. For example, the number of nonterminals increases by at most a factor of 2 when GNF is used. For weak GNF-grammars the number of productions goes up from n to at most \(O(n^ 3)\) and examples are given where \(\Omega (n^ 2)\) are needed. The same result holds for the total length of grammars. Transformation into position restricted grammars may rise the number of productions or nonterminals from n to any arbitrary high value, i.e. it cannot be bounded by any function on n. However the total length of the grammar goes up by at most a constant factor for some special cases of position restricted grammars especially for Chomsky normal form.