Search

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.

The relationship between the set of productions of a context-free grammar and the corresponding set of defining equations is first pointed out. The closure operation on a matrix of strings is defined and this concept is used to formalize the solution to a set of linear equations. A procedure is then given for rewriting a context-free grammar in Greibach normal form, where the replacements string of each production begins with a terminal symbol. An additional procedure is given for rewriting the grammar so that each replacement string both begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular expressions over the total vocabulary of the grammar, as is required by Greibach's procedure.

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