Membership and Finiteness Problems for Rational Sets of Regular Languages

摘要

Let Σ be a finite alphabet. A set R of regular languages over Σ is called rational if there exists a finite set ε of regular languages over Σ, such that R is a rational subset of the finitely generated semigroup (S, ·) = < ε > with £ as the set of generators and language concatenation as a product. We prove that for any rational set R and any regular language R is contained in Σ~* it is decidable (1) whether R ∈ R or not, and (2) whether R is finite or not.