Relatively Disjunctive Languages and Relatively Regular Languages

In this chapter, we will investigate relatively regular languages and relatively disjunctive languages systematically. The two classes of languages are natural generalizations of regular languages and disjunctive languages respectively and relatively disjunctive languages are even a generalization of f-disjunctive languages discussed in the previous chapter. One of the main results of the chapter is that “In any finite alphabet, all languages are divided into two disjoint classes: relatively regular languages and relatively disjunctive languages”. This is a natural generalization of the classification of languages on one-letter alphabets, and in some sense, gives a corresponding classification of languages on finite alphabets.