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.

This paper deals with the question of canonical types for grammar forms and grammars. A grammar (form) is called position restricted of type (m1,…,mn+ 1) if n⩾2, each m1 is a nonnegative integer, and each production is either of the type ξ0 → u, u a terminal word, or ξ0→w1ξ1w2⋯wnξnwn+1, where each ξ is a variable and each wi is a terminal word of length mi. Thus a grammar (form) is position restricted if all productions in it but the terminal ones have the same relative position of terminals and variables. The main results are as follows. Each grammar form G1 is equivalent to a grammar form G2 of any desired position-restricted type (m1,…,mn,0), with the interpretation grammars of G2 of position-restricted type (m1,…,mn,0) being sufficient to define all languages in L(G1). The above result is no longer true if the position-restricted type is such that mn+1⩾1. The second main result is that each context-free language is defined by a grammar G of any desired position-restricted type.

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).