Search

A weakly conditional grammar is specified as a pair K=G, G' where G is a context-free grammar, and G' is a regular grammar such that a production rule of G is only applicable to the sentential form if it belongs to the language generated by G'. The nonterminal complexity VarK of the grammar K is defined as the sum of the numbers of nonterminals of G and G'. This paper studies the nonterminal complexity of weakly conditional grammars, and it proves that every recursively enumerable language can be generated by a weakly conditional grammar with no more than ten nonterminals. Moreover, it shows that the number of nonterminals in such grammars without erasing rules leads to an infinite hierarchy of families of languages generated by weakly conditional grammars.

This chapter contains sections titled: Introduction Grammars for Arithmetic Expressions Specifying Associativity and Precedence in Grammars Backus-Naur Form Syntax Diagrams Abstract Syntax Trees and Three-Address Code Noncontracting Grammars Essentially Noncontracting Grammars Converting a Context-Free Grammar to an Essentially Noncontracting Grammar Pumping Property of Context-Free Languages (Optional) Problems

An interpretation of a grammar form is called (k, i)-bounded iff all its nonterminals are substituted by at most k symbols and all its terminals are replaced by at most i words. The (k, i)-bounded grammar family of a grammar form is the collection of its (k, i)-bounded interpretations, and its (k, i)-bounded grammatical family is the corresponding family of languages. The paper gives basic properties of these families. Especially, we show the decidability of the equivalence problem for bounded grammar families, the undecidability of the membership problem for bounded language families and give some hierarchy, closure and descriptional complexity results. Finally, some consequences in normal form theory of context-free languages are presented.

It is shown that the set of all interpretations of one (or of all) context-free grammar forms modulo strong equivalence is a distributive lattice with respect to the ordering relation “is an interpretation of”. It is also established that for each context-free grammar form there exists a unique (up to “pseudo-isomorphism”) symbol-tight, strongly equivalent context-free grammar form which is minimal with respect to the number of productions.

Each context-free grammar can be transformed to a context-free grammar in Greibach normal form, that is, a context-free grammar where each right-hand side of a prorfuction begins with a terminal symbol and the remainder of the right-hand side consists of nonterminal symbols. In this short paper we show that for a left-regular grammar G we can obtain a right-regular grammar G’ (which is by definition in Greibach normal form) which left-to-right covers G (in this case left parses of G’ can be mapped by a homomorphism on right parses of G. Moreover, it is possible to obtain a context-free grammar G��? in Greibach normal form which right covers the left-regular grammar G (in this case right parses of G��? are mapped on right parses of G).