Context-free grammar forms

摘要

In an attempt to provide a unified theory of grammars, a model is introduced which has two components. The first is a “grammar form,” which provides the general structure of the productions in the grammars to be defined. The second is an “interpretation”, which yields a specific grammar. By considering all interpretations, a family of grammars, intimately related to that of the grammar form, is obtained. Many of the well-known families of grammars occur as special instances.Attention is focused on the situation when the productions in the grammar form are context free. Necessary and sufficient conditions on a context-free grammar form are given in order for it, to yield, respectively, exactly the finite languages, the regular sets, the linear context-free languages, and all the context-free languages. Each context-free grammar form can be replaced by another, yielding the same family of languages, in which the underlying grammar is sequential. Of special interest to language theory is the fact the family of languages obtained from each context-free grammar form is a full principal semi-AFL.