Languages defined by pure patterns

Abstract

Angluin’s pattern languages that use pattern strings as language descriptors, have motivated researchers in formal language theory to introduce and investigate grammars based on patterns. Both theoretical as well as application oriented properties of these grammars have been studied. On the other hand pure grammars in line with the early works of Thue have been proposed and studied for their properties. Here we introduce a new kind of language generative device, called a pure pattern grammar, linking the notions of pattern and pure grammars. Two modes of derivation in such a pattern grammar, called as synchronized and non-synchronized modes, are introduced. The resultant families of languages are compared for their generative power with certain other well-known families of languages. Certain closure properties and descriptional complexity results are also obtained.