Property grammars and table machines

The purpose of this paper is to generalize the methods of automata theory to accommodate infinite input alphabets and to propose a method of describing computer languages such as ALGOL-60 with more reliance on grammatical methods and less reliance on semantic constraints. Our chief concern is a natural generalization of a context-free grammar which we call a context-free property grammar. The generalization is straight-forward and can be used in similar fashion to define regular property grammars, context-sensitive property grammars, etc. The chief result is that these contextfree property grammars generate precisely the set of languages recognized by a non-determinated pushdown table machine, which is a straight forward generalization of a pushdown machine. Again it is clear that other kinds of automata have corresponding table versions. The language-machine correspondence is preserved in such a matter that efficient processing schemes for context-free property grammars are suggested by the well-known schemes for context free languages. Before beginning, we mention some mathematical conventions used. If A is a set, then A* represents the set of all finite sequences of elements from A. If w is in A*, then l(w) is the length of word w. The symbol ∈ represents the null or length zero word. A typical element of A* will be described by ai...an with the understanding that if n = 0, the null string ∈ is represented and there are no ai in the string. If n is a positive integer, then An represents the set of n dimensional vectors whose components are from A. A typical element of An is represented as (ai,..., an). If I is a set, then AI represents the set of all functions from I to A. Finally 2A represents the set of all subsets of A.