\(\mathcal {P}\mathcal {S}\) -Regular Languages

In this chapter, by using “permissible subsets”, we obtain a kind of generalized principal congruences determined by languages. Applying this kind of generalized principal congruences, we introduce and investigate a class of generalized regular languages, namely, \(\mathcal {P}\mathcal {S}\) -regular languages. We give some characterizations of such generalized regular languages. As applications of the results, we obtain some characterizations of regular languages. Also, we consider the closure properties of the class of \(\mathcal {P}\mathcal {S}\) -regular languages, and the relationship among \(\mathcal {P}\mathcal {S}\) -regular languages, context-free languages and context-sensitive languages. As usual, A is always a finite alphabet throughout this chapter.