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 paper is concerned with the following problem: Given a context-free grammar G , find a context-free grammar with the fewest nonterminal symbols or with the fewest rules that is equivalent to G . A reduction procedure is presented for finding such a reduced context-free grammar that is structurally equivalent to a given G . On the other hand, it is proved that there is no finite procedure for finding such a reduced context-free grammar that is weakly equivalent to a given G .

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.