Operations Which Preserve Definability in Languages
Seymour Ginsburg, Gene F. Rose · Journal of the ACM · 1963
To better understand the syntax of problem-oriented languages, the equational form used in defining ALGOL [1] was recently abstracted [6].On varying the coefficients in the abstract equational form two families of languages arose.[A language is viewed as a set of strings, called words, of symbols from a finite, fixed alphabet.]The two types of languages, called definable and sequentially definable, were then investigated and a number of properties discovered.In particular, it was shown that the definable languages were identical to the type-two phrase structure languages introduced by Chomsky [4].The present paper deals with operations T (on languages) which preserve definability ~nd frequently sequential definability.All operations considered have the additional property of preserving regularity [7]--the interest in regular sets stemming from the fact that they have been considered as "finite state languages" [3].Two basic results are proved.The first (Theorem 2.1) permits derivation of (sequential) definability-preserving operations from other (sequential) definability-preserving operations.The second (Theorem 3.1) asserts that a sequential machine always changes a definable set into a definable set (but not necessarily a sequentially definable set into a sequentially definable set).Using these two results, a large number of specific operations-many occurring in data processing--arc shown to preserve definability and, depending on the operation, sequential definability.In addition to the two main results there occur in appendices A and B necessary conditions for a set to be sequentiMly definable and definable respectively.The former is the first known necessary condition for sequentially definable sets which differs from those for definable sets.It is anticipated that many of the operations considered here will be useful in later studies of problem oriented languages.