X-Families: An Approach to the Study of Families of Syntactically Similar Languages

Abstract

All classes of grammars investigated in formal language theory generate a language by starting from finite sets of axioms and iteratively applying certain production rules which transform “correct” strings into “correct” strings. If the set of rules is fixed and the axiom set is varying over the family of finite languages, then to any grammar we associate a family of languages. When using grammars of certain type X, we call this family an X-family. The aim of this paper is to propose the investigation of such families of languages. We only formulate here some of the basic problems and we start the study of M-families, those obtained when using Marcus contextual grammars as starting point. Several properties of M-families are given, examples and counterexamples are produced, and some decidability results are proven.